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)
Heuristics
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:
- is closed under products
- 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.
Best Answer
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$.