Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Euclid's proof is typically regarded as very weak, because it produces a density which is extremely thin. My question is how far the most obvious generalizations of Euclid's algorithms (for definiteness, algorithm E2) partially fix this problem. In particular, does E2 produce a smooth monotone $\pi(n)$ which asymptotically grows at least like log(N)?

The algorithms which to me are the obvious generalizations:

  • E1. Given a set P of primes, partition it into into two parts A and B, multiply the primes in A and the primes in B, and either add or subtract the two products. These $2^{|P|}$ numbers are all coprime to all the numbers in P.

  • E2. Given any partition of P into K disjoint subsets $A_1, \ldots , A_K$, Generate $E_k(A_k) = \sum_{1\le k\le K} {\pm (k)} \prod_{p \in (P-A_k)} p $,
    where ${\pm(k)}$ is a sign for each partition. In words: multiply all the primes in the complement of each partition and add the results with arbitrary signs. These are all coprime too.

  • E3. Given any list of K exponents $e(p,k)$ for each prime p and $k\in {1..K}$, where for each fixed p, exactly one of the e(p,k) is zero, the broadest reasonable generalization is to generate coprime numbers with multiplicity:
    $E_k(A_k,e) = \sum_{1\le k\le K} {\pm (k)} \prod_{p\in P} p^{e(p,k)} $

Algorithm E3 produces an infinite list of coprimes, so consider E2. Starting with the set {2}, and applying algorithm E2, you get a very dense list of new primes, at least for a while. I am asking the weakest question I can think of, namely does E2 produces a better than 1/x density, and a better than logarithmic growth for the prime counting function, when iterated from an initial segment of primes:

Question: Does algorithm E2 produce enough new coprimes to prove that p(x)> clog(x)


The reason I am asking for such weak growth is because of the following (very bad, but perhaps essentially accurate) heuristic: let $\pi(N)$ be the prime counting number, and partition the primes less than $N$ into subsets of just one prime. There are about $2^{\pi(N)}$ E2 coprimes of this form, and I will only consider these. I will assume that all they are all distinct, and prime, since when they factor, they make more primes. So that, calling P(N) the product of all primes less than N

$\pi(P) >\approx 2^{\pi(N)}$

which, since $P = (2^{\pi(N)}) ^{\overline{\log_2 p}}$, where $\overline{\log_2 p}$ is the mean of the base two logarithm of all primes less than N. Assuming that the average log is $\log_2(N)$ (which overestimates \pi(N), one finds

$\pi((2^{\pi(N)})^{\log_2 N} ) \approx 2^{\pi(N)}$

which, calling the big number $2^{\pi(N)}$ by the name A, says that

$\pi(A^{\log_2(N)}) \approx A$

and noting that N is about log(A) up to what matters, one finds that

$\pi(A^{\log_2(\log_2(A))}) = A$

so that the heuristic lower bound for $\pi(x)$ is asymptotically approximately the inverse function of $x^{\log_2(\log_2(x))}$, i.e. eventually approximately logarithmic.

(the motivation for this question is an [What are some proofs of Godel's Theorem which are *essentially different* from the original proof? unrelated answer] to an unrelated question)

Embarassing Omission

LATER EDIT: I thought E2 was the interesting algorithm, but set of numbers generated by E3:

  1. is closed under products
  2. is closed under adding multiples of P, where P is the product of all the primes in the original set.

So the only way it can fail to generate the full multiplicative group mod P is if by some miracle it stays in a multiplicative subgroup, and that's ridiculous, but ridiculous is not a proof. Given this the restriction of multiplicity to get E2 starts to look completely artificial.

At least this easier observation would completely answer the original nebulous motivating question: Euclid's proof, when turned into the most general equivalent algorithm, does generate all the primes by finding the next primes for any given collection of primes (but one needs an exponent bound to make the algorithm effective). So, I guess a much better question would be the following conjecture:

Q2(conjecture): E3 starting with an initial set of primes gives all the coprimes.

share|improve this question
1. This question is way too long, I advise you to trim for everyone's benefit. 2. there's a small fallacy: "and prime (if they factor, they only make more)". What if they aren't prime and share all prime factors? The absurd case is that all "Euclid numbers" are a power of a new prime. (*) Not trying to make conversation in the comments. –  Dror Speiser Aug 9 '11 at 11:04
Standard notation for your p(N) and P(N+1): $\pi(N)$ and $N\#=\exp(\vartheta(N))$. –  Charles Aug 9 '11 at 14:24
I'm not sure about the heuristic either. $\pi(A^{\lg N})=\pi(2^{\pi(N)\lg N})=\pi(N^{\pi(N)})$ which will be quite a bit larger than $A=2^{\pi(N)}$ for N > 20, say. –  Charles Aug 9 '11 at 14:38
@Dror:1. Done. 2. There are much more serious problems with this heuristic, it is not quite self-consistent. I "feel" it is asymptotically right, but it is not even convincing at the heuristic level. –  Ron Maimon Aug 9 '11 at 15:00
Dear Ron, I don't think you hit CW. Rather, if you make (more than?) eight edits to one of your posts, it automatically becomes CW. (And my understanding is that the moderators can't change this.) Regards, –  Emerton Aug 9 '11 at 15:23

1 Answer 1

up vote 2 down vote accepted

You might be interested in the papers Guy, Lacampagne, and Selfridge, Primes at a glance, Math. Comp. 48 (1987) 183-202, and Agoh, Erdos, and Granville, Primes at a (somewhat lengthy) glance, Amer. Math. Monthly 104 (1997) 943-945. In the second paper, it is proved that, given $p_1=2\lt p_2=3\lt\cdots\lt p_k$, the first $k$ primes, and a positive integer $n\le(\prod_{i=1}^kp_i)(\sum_{j=1}^k1/p_j)$, free of prime factors less than or equal to $p_k$, there exist integers $N_1,N_2,\dots,N_k$ with $$n=N_1+N_2+\cdots+N_k$$ where each $|N_j|\lt\prod_{i=1}^kp_i$ and the prime divisors of $N_j$ are precisely the primes $p_1,p_2,\dots,p_k$ other than $p_j$.

The earlier paper looked at writing $n=A\pm B$ where each prime not exceeding $\sqrt n$ divides exactly one of $A$ and $B$.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.