Calcul de la fonction Mobius

13

La fonction Mobius est définie comme , si a un facteur premier carré, et si tous les nombres premiers sont différents. Est-il possible de calculer sans calculer la factorisation première de ? $\mu(n)$ $\mu(1)=1$ $\mu(n)=0$ $n$ $\mu(p_1 \dots p_k)= (-1)^k$ $p_1,\dots,p_k$ $\mu(n)$ $n$

comp-number-theory Craig Feinstein
la source

6

Je pense qu'il demande simplement s'il existe un moyen de calculer

μ (n)

$\mu(n)$ qui n'est pas connu pour fournir également une factorisation.

Suresh Venkat

2

@Kaveh, je ne parle pas ici de complexité informatique. Suresh a raison dans son interprétation. Cela revient à déterminer qu'un nombre est composite sans déterminer sa factorisation. Peut-on faire quelque chose comme ça pour la fonction Mobius?

Craig Feinstein

1

Je ne pense pas que ce soit une vraie question. J'ai pensé qu'il pourrait être utile de vous rappeler que sur cstheory, nous avons une politique stricte contre les sujets conviviaux au cas où vous essayez de faire de la publicité pour les idées contenues dans ces derniers .

Kaveh

3

@Kaveh, j'ai posé une question sérieuse qui a obtenu 4 pouces. Bien sûr, ma réponse a obtenu 8 pouces, mais c'est la vie. Je ne connaissais ma réponse à la question qu'aujourd'hui, alors j'ai posté la réponse. Il me semble que vous essayez de m'ostraciser en prétendant que j'ai ici une sorte d'arrière-pensée. Je peux vous assurer que je n'ai pas d'autre motif que d'obtenir une réponse à la question.

Craig Feinstein

5

@Kaveh: L'OP est un trisecteur bien connu, sur plusieurs forums. Cela dit, l'avez-vous déjà vu être impoli envers quelqu'un? Non. Il comprend simplement mal ce que signifie prouver des limites inférieures. La question me semble sur le sujet. Il y a un dicton: "Même une horloge arrêtée a raison deux fois par jour".

Aaron Sterling

34

Une non-réponse à votre question est que SQUARE-FREE (est un nombre sans carré) n'est lui-même pas connu pour être en P, et le calcul de la fonction Möbius résoudrait ce problème (puisqu'un nombre sans carré a ). $\mu(n) \neq 0$

Suresh Venkat
la source

7

Connaissez-vous des articles qui discutent de la complexité de l'absence de carré? tout ce que j'ai pu trouver est le suivant: dl.acm.org/citation.cfm?id=371327&dl=GUIDE&coll=GUIDE , qui donne des limites inférieures à la taille de la formule. en regardant mathoverflow.net/questions/16098/… , je pense que l'on ne sait pas grand-chose sur la possibilité de réduire l'affacturage au carré.

Sasho Nikolov

15

Pour une autre non-réponse, vous pourriez être intéressé par la conjecture de Sarnak (voir par exemple http://gilkalai.wordpress.com/2011/02/21/the-ac0-prime-number-conjecture/ , http: //rjlipton.wordpress .com / 2011/02/23 / the-depth-of-the-mobius-function / , /mathpro/57543/walsh-fourier-transform-of-the-mobius-function ), qui indique essentiellement que la fonction de Möbius n'est corrélée avec aucune fonction booléenne «simple». Il n'est pas déraisonnable de s'attendre à ce qu'il tienne lorsque «simple» est interprété comme du temps polynomial. Ce que nous savons jusqu'à présent, c'est que la conjecture vaut pour les fonctions (prouvées par Ben Green ), et toutes les fonctions monotones (prouvées par Jean Bourgain ). $\mathrm{AC}^0$

Emil Jeřábek 3.0
la source

4

Je pense que c'est le livre de Ben Green: arxiv.org/abs/1103.4991

Suresh Venkat

0

L'une des formules récursives reliant les valeurs de la fonction mobious est

\sum_{m \leq n} ⌊ \frac{n}{m} ⌋ μ (m) = 1.

$\sum_{m \leq n} \left\lfloor \dfrac {n}{m} \right\rfloor \mu (m) = 1.$ Mais pour trouver le

μ (n)

$\mu(n)$ nous devons connaître les valeurs mobious pour

m < n

$m < n$ . Donc

μ (n) = 1 - \sum_{m < n} ⌊ \frac{n}{m} ⌋ μ (m) .

$\mu (n) =1-\sum_{m < n} \left \lfloor \dfrac {n}{m}\right \rfloor \mu (m) .$ Ici, nous divisons

n

$n$ par les plus petits entiers positifs

m < n

$m<n$ , nous n'avons pas besoin de savoir s'ils sont des facteurs de

n

$n$ lorsque

m

$m$ a un facteur carré! (

μ (m) = 0

$\mu(m)=0$ ), Mais encore faut-il connaître les facteurs de

m

$m$ pour conclure ceci !! On a donc:

\begin{aligned} μ (n) = & 1 - \sum_{a_{1} < n} ⌊ \frac{n}{a_{1}} ⌋ \\ + & \sum_{a_{1} < n} ⌊ \frac{n}{a_{1}} ⌋ \sum_{a_{2} < a_{1}} ⌊ \frac{a_{1}}{a_{2}} ⌋ \\ - & \sum_{a_{1} < n} ⌊ \frac{n}{a_{1}} ⌋ \sum_{a_{2} < a_{1}} ⌊ \frac{a_{1}}{a_{2}} ⌋ \sum_{a_{3} < a_{2}} ⌊ \frac{a_{2}}{a_{3}} ⌋ + \dots \end{aligned}

$\begin{align} \mu(n)=&1-\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor \\ +&\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor \sum_{a_2< a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor \\ -&\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor \sum_{a_2< a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor \sum_{a_3< a_2} \left \lfloor \dfrac {a_2}{a_3}\right \rfloor + \cdots \end{align}$ Reportez-vous à cet article:https://projecteuclid.org/euclid.mjms/1513306829pour la preuve de la formule.

Hunde Eba
la source

n = 120

$n=120$

Vérifiez la version éditée !! @Craig

Hunde Eba

-22

$n=p_1 \dots p_k$ $p_j$

μ (n) = μ (p_{1} \dots p_{k}) = μ (p_{1}) \dots μ (p_{k}) .

$\mu(n)=\mu(p_1 \dots p_k)=\mu(p_1)\dots \mu(p_k).$

μ (n)

$\mu(n)$

μ (p_{j})

$\mu(p_j)$ for each

p_{j}

$p_j$ . This implicitly requires recognizing that

p_{1} \dots p_{k}

$p_1 \dots p_k$ is the prime factorization of

n

$n$ .

Here's an analogy: In order to know whether there are an odd or even number of jelly beans in a jar, one must count the jelly beans. This is why you must compute the prime factorization of a number to compute its Mobius function, when it is not divisible by a square. But in order to know that there is more than one jelly bean in a jar, one does not need to examine any of the jelly beans in the jar. One can just shake the jar and hear that there is more than one jelly bean. This is why you don't have to factor a number to know it is composite. Algorithms like Fermat's Little Theorem allow one to "shake the number up" to know it is composite.

When $n$ is divisible by a square, you don't have to compute the prime factorization of $n$ . But you do have to find a nontrivial factor of $n$ : If $n$ is square, in order to determine that it is square, you have to take its square root, in which you find a nontirival factor of $n$ . A fortiori, if $n$ is not a square but is still not squarefree, in order to determine that $\mu(n)=0$ , it is necessary to find a nontrivial factor of $n$ .

Craig Feinstein
la source

6

@Craig It is still wrong. You could use the same (fallacious) argument for the composite testing problem as Peter Shor said. You're basically giving an algorithm for your problem and stating that it is the only way to proceed. Showing that an obvious algorithm is the best to solve a problem is one of the biggest challenge in complexity theory.

Michael Blondin

6

I will try to give an example. Consider the problem of multiplying two matrices A and B of size

n \times n

$n \times n$ . The definition of AB is

(A B)_{i, j} = \sum_{k = 1}^{n} A_{i, k} \cdot B_{k, j}

$(AB)_{i,j} = \sum_{k=1}^n A_{i,k} \cdot B_{k,j}$ . Therefore, by an argument of your type, this would imply that AB must necessarily be computed in time

O (n^{3})

$O(n^3)$ from its definition. However, it is well-known that AB can be computed in time

O (n^{2.807})

$O(n^{2.807})$ . If you can see how the so-called argument fails here, you should be able to see how it fails in your answer.

Michael Blondin

14

Re "In order to know whether there are an odd or even number of jelly beans in a jar, one must count the jelly beans." — even this is not true. You could pull them out in pairs (one for me one for you...) without actually counting them as you go. Then when you have run out of pairs to pull, you have either zero or one left and you know the parity.

David Eppstein

12

For a problem where counting is hard but parity is easy, consider the permanent of a 0-1 matrix

M

$M$ . (This is the same as the number of perfect matchings in a bipartite graph.) The parity of the permanent is the same as the parity of the determinant, which can be computed in polynomial time. But evaluating the permanent is #P-complete, and thus NP-hard.

Peter Shor

6

Craig, without factoring it into primes, yes, by computing integer square root (known to be computable in polynomial time unlike factoring) it's 69^2. I do not have to factor 69. Your beans argument suggests that factoring is mandatory, since you have to look at every jelly to check if every flavour occurs even number of times.

sdcvvc

Calcul de la fonction Mobius

Réponses: