Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Energy counterexample
Statement and scope
Proved. There are finite systems of distinct singleton moduli, with
the original activation rule, and cutoffs Q→∞ such that
E:=q∑eqlogq⟶2log2,HB(Q)−βHQ∼(logQ)1/21⟶∞.(1)
Here B is the delayed excluded union, β is the full periodic
union measure, and eq are the full first-kill measures in increasing
modulus order. All the moduli are at most Q.
Consequently there is no absolute C for which
HB(X)≤βH⌊X⌋+C1+q≤X∑eqlogq(2)
holds for every finite distinct-modulus singleton system. This accounts
for the entire preparatory sieve, not just the late first-kill cells.
The construction also refutes a uniform additive O(loglogX)
error and the proposed rank-sensitive error Cr=exp(o(r)).
This is not an infinite counterexample to Problem 25. Its normalized
harmonic excess tends to zero. A uniform additive o(logX) estimate
and the constant first-kill entropy bound remain open.
The rank-filtered refinement below
increases the attainable lower-bound exponent to every
γ<(721/7−331/3−3)/4=0.100469…,
still with energy tending to 2log2. It does not contradict the
weaker square-root energy target.
A sparse divisor-residue channel
Let L=2k and Q>L be integers. For each odd residue
r∈{1,…,L−1}, put
Dr={q∈N:L<q≤Q,q≡r(modL)},br=μq∈Dr⋃qZ.
We claim that some such r satisfies
br≪L−1/2(log(2Q))2−1.(3)
The implied constant is absolute.
For every odd prime p≤Q, independently choose a nonnegative
integer Vp with
Pr(Vp=v)=(1−1/p)p−v,M=p≤Qp=2∏pVp.
These are precisely the finite-dimensional Haar valuation laws. Every
q∈Dr is odd and has all prime factors at most Q, so
br=Pr(∃q∈Dr:q∣M).
For each realization of M, at most
min(φ(L),τ(M)) unit residues modulo L occur among its
divisors in (L,Q]. Here τ is the number of positive divisors.
Consequently
The divisor moment factors over the independent valuations. For p≥3,
(1−1/p)v≥0∑v+1p−v=1+p2−1+O(p−2).
The remainder is bounded uniformly in p: the terms v≥2 have sum
O(p−2). Comparison with the local factors of
∏p≤Q(1−1/p)−(2−1) therefore gives
Eτ(M)≪p≤Q∏(1−1/p)−(2−1)≪(log(2Q))2−1.(5)
The last bound is the elementary Euler-product estimate proved in
coprime entropy.
Equations (4)--(5), together with φ(L)=L/2, prove (3).
No distribution theorem for primes in arithmetic progressions is used.
From now on choose
Q=⌊exp(L21/20)⌋
and choose the least odd r minimizing br. This is a finite,
deterministic choice: each br is the exact proportion of covered
residues in a finite common period. The minimum satisfies (3). Since
2−1<5/12, we obtain
br≪L−1/2+(21/20)(5/12)=L−1/16.(6)
The finite congruence system
First install the k classes
Cj=[2j−1−1]2j,1≤j≤k.(7)
These are disjoint full cylinders: membership is equivalent to
v2(n+1)=j−1. Their full survivor set is the single fiber
[−1]L, of measure 1/L.
Set
α=L−1−r∈[0,L−2],
and then install one class
[α]q(q∈Dr).(8)
All new moduli are odd and greater than L, whereas the old moduli
are the distinct powers of two at most L. Thus all moduli are
globally distinct and all old classes precede the new ones in increasing
modulus order. The residues in both (7) and (8) are normalized; in
particular 0≤α<q for every new class.
The full union in (8) is the common translate by α of the
multiples union generated by Dr, hence has measure br.
Because all its moduli are odd, this event is independent of the
2-adic fiber [−1]L. The final full survivor measure is therefore
exactly
δ=1−β=L1−br.(9)
Exact delayed survivors and activation
The positive roots omitted by the delayed versions of the old classes
are
2h−1,1≤h≤k−1.
They are not covered by another old class, since the full old cylinders
are disjoint. Every new modulus exceeds L, so no new class is active
at these roots. The remaining old delayed survivors are the positive
integers in [−1]L.
The first positive point of this fiber is L−1. For every later one,
write
n=Lt+L−1,t≥1.
If n≤Q, then
q=n−α=Lt+r
satisfies L<q≤n≤Q and q≡r(modL), so q∈Dr.
Moreover n=q+α is precisely the first active endpoint of its
new class. This checks activation without any change of cutoff or
delay convention.
Thus the delayed survivor set A satisfies the exact identity
A∩[1,Q]={2h−1:1≤h≤k},HA(Q)=h=1∑k2h−11<2.(10)
Bounded total first-kill energy
Since the old full cylinders are disjoint, their first-kill measures
are 2−j. Their energy is
Eold=log2j=1∑k2jj=(2−Lk+2)log2.(11)
The sum of all the new first-kill measures is exactly the increment
in full union measure, namely br/L. All new moduli are at most
Q, so (6) gives
0≤Enew≤LbrlogQ≪L−1/16+1/20=L−1/80.(12)
Together (11)--(12) prove E→2log2.
On the other hand, (9)--(10) give
HB(Q)−βHQ=δHQ−HA(Q)≥(1−br)L1/20−2,(13)
because HQ≥log(Q+1)>L21/20. In fact, using
HQ=logQ+O(1) and br=o(1), this excess is
(1+o(1))L1/20=(1+o(1))(logQ)1/21.(14)
This proves (1), disproves (2), and disproves a uniform additive
O(loglogX) error.
Consequence for the rank-sensitive target
The later prime-only amplification
supersedes the rank-constant obstruction in this section: no finite
rank-only additive bound exists, already at rank one. The construction
here still has the distinct additional feature of bounded first-kill
energy, and the calculations below remain valid.
the union B>R of classes whose moduli have Ω(q)>R has
HB>R(Q)=O(1), uniformly over finite singleton families.
Explicitly its bound is
HB>R(Q)≪(3/2)−R(log(3Q))5/2=O(1).
Delete those high-rank classes from the construction and write
B≤R and β≤R for the remaining delayed union and
full union measure. Removing classes can only decrease Haar measure,
and loses at most O(1) harmonic mass. Consequently
HB≤R(Q)−β≤RHQ≥HB(Q)−βHQ−O(1)≫L1/20.(15)
Since R=(42/5)logL+O(1), any universal bounds
HB(X)≤βH⌊X⌋+CRfor all systems with Ω(q)≤R
must therefore satisfy, along this sequence,
CR≥exp((1/168+o(1))R).(16)
In particular CR=exp(o(R)) is impossible. This does not contradict
the bounded-rank natural-density theorem, which does not assert such
a uniform additive error.
Why this does not resolve Problem 25
The normalized excess is
HQHB(Q)−βHQ=L1−br−HQHA(Q)∼L1⟶0.
Thus these finite systems do not produce a fixed positive logarithmic
excess. Also, combining gadgets while retaining their preparatory
classes for unbounded k retains every class in (7). Those classes
already have full Haar union measure one; their delayed survivor set
is contained in {2h−1:h≥1} and has natural density zero.
Any additional deletions preserve that zero density. This direct
combination therefore cannot give the required infinite counterexample.
The spectral conductor-energy inequality remains valid. What fails is
its proposed uniform conversion to harmonic discrepancy. Neither a
uniform additive o(logX) bound nor the constant first-kill entropy
target is refuted by this construction.
Two linear entropy charges also fail
The same example refutes linear charging of the unnormalized
first-kill relative entropy either by the reciprocal sum or by the
first-kill energy. This does not refute the constant normalized entropy
target.
Let I index the new odd-modulus classes, and put
ci=HEi(Q)/HQ. Their exact endpoint deletion gives
On the other hand, summing along the single residue channel gives
i∑qi1≍1+LlogQ≍L1/20,
while (11)--(12) show ∑ieilogqi→2log2. Thus neither
of these costs can bound (17) up to an absolute linear factor, even
after adding an absolute constant. The lower bound after normalization
by HQ is only ≫(logL)/L, which tends to zero; it remains
compatible with a universal bound for ∑icilog+(ci/ei).
Optimizing the divisor moment
The exponent 1/21 can be slightly improved without changing the
construction. For every fixed 0<θ<1, replace the square root
in (4) by the θth power. The local factors are
(1−1/p)v≥0∑(v+1)θp−v=1+(2θ−1)/p+Oθ(p−2),
so the same proof gives
br≪θL−θ(log(2Q))2θ−1.
Choose Q=⌊exp(La)⌋ with a>1. The new energy is
then at most a constant times
La2θ−θ−1.
It tends to zero if a<(1+θ)/2θ, while the harmonic excess
is asymptotic to La−1. Elementary differentiation gives
0<θ<1max2θ1+θ=elog22,θmax=log21−1.
Thus for every fixed
0<γ<1−2elog2
there are systems with E→2log2 and excess
≍(logQ)γ. All activation and distinctness checks are
unchanged. This remains sublogarithmic and does not give an infinite
counterexample. The prepared-block entropy bound
also shows that this mechanism's normalized entropy is small, even
after optimizing its parameters.
Rank-filtered residue channels
Theorem. For every
0<γ<γ∗:=4721/7−331/3−3=0.100469471…,(18)
there are finite distinct-singleton systems with cutoffs Q→∞
and original activation such that
E⟶2log2,HB(Q)−βHQ≥(logQ)γ.(19)
Only a lower bound for the excess is claimed here, unlike the
asymptotic equivalence in (1).
Write L=2k, H=logQ, and fix c>1, to be chosen below.
Put
For the last estimate, independence and the uniform local expansion give
(1−1/p)v≥0∑(2v+1−1)1/3p−v=1+p31/3−1+O(p−2).
The remainder is uniform for p≥3, since 21/3<3.
The elementary Euler-product bound then gives the power
H31/3−1; the factor 2−R/3 supplies the remaining
term in A.
Enough channels retain reciprocal mass
Set Y=(Q−L)1/R and
S=R2<p≤Y∑p1=logH−O(loglogH).
The last equality follows from
∑p≤x1/p=loglogx+O(1), itself a consequence of the
two-sided elementary Euler-product estimates used earlier.
Products of R distinct primes from this interval are odd, at
most Q−L, and greater than L: their minimum logarithm is
greater than 2RlogR, whereas logL=O(logH).
Sampling R primes independently with weights 1/(pS), the
collision probability is at most
(2R)S−2p>R2∑p−2=O(S−2)=o(1).
Unique factorization therefore gives
r∑mr≥(1−o(1))R!SR=H1−I(c)+o(1).(22)
No prime distribution in residue classes is used here.
For definiteness let s=SR/(2R!), so (22) is at least s
for all sufficiently large Q. Define
G={r:mr≥s/L}.
The other channels contribute at most s/2, because there are
L/2 odd channels. Uniformly mr≤CH/L, by summing the
progression r+tL, t≥1. Hence
∣G∣≫Ls/H=LH−I(c)+o(1).
Choose the least-footprint channel in G. Equation (21)
then proves the simultaneous estimates
mr≥LH1−I(c)+o(1),br≪L−1/3HA+I(c)+o(1).(23)
The extra HI(c)+o(1) in the footprint is the cost of
restricting to large-mass channels; it is not discarded.
Installing the filtered channel
Use the binary preparation (7), leaving the full fiber [−1]L,
and put α=L−1−r∈[0,L−2]. Append
[α]q for q∈Dr. All new moduli are odd and exceed
the old moduli. They are distinct, and every residue is normalized.
Each distinct endpoint
n=q+α≤Q
lies in the old survivor fiber and is active at its own modulus.
Its reciprocal mass, summed over Dr, is
q∈Dr∑q+α1=mr−O(1/L);
indeed ∑q>L,q≡r(L)α/q2=O(1/L).
Other appended congruences may also cover these points, which only
helps the union count.
The new union has density br on the odd-prime coordinates and
is independent of the binary fiber. Thus its incremental measure is
br/L, and its entire first-kill energy is at most
Enew≤brH/L.(24)
The old energy tends to 2log2. Its delayed survivor harmonic
mass is at most HQ/L+3: the progression [−1]L costs
at most HQ/L+1, and the inactive roots 2j−1 cost less
than two. Its harmonic discrepancy is consequently at least −3.
It follows that the final discrepancy is at least
−3+mr−O(1/L)−LbrHQ.(25)
Choose a fixed η>0 and
Q=⌊exp(L1/η)⌋. Then
L=Hη+o(1). By (23)--(24), the new energy tends to zero
if
Under this condition, (23) and (25) give an excess lower bound
H1−I(c)−η+o(1)−O(1).
The supremum of its exponent allowed by (26) is
1−I(c)−ηcrit(c)=44−331/3+clog2−7I(c).
This expression is maximized at c=21/7, since its derivative
has the sign of log2−7logc. Substitution gives (18).
For every smaller γ, choose η with strict margins
in (26) and 1−I(c)−η>γ. This proves (19).
The examples do not refute the
square-root energy estimate.
For these parameters η>1/2, while the trivial upper bound
for positive excess is
(HB(Q)−βHQ)+≤(1−β)HQ≤HQ/L=H1−η+o(1)=o(H).
Nor do these finite systems produce positive normalized logarithmic
excess. The general conditioned-tail and square-root estimates remain
unresolved.
One fixed family can have finite energy and unbounded additive excess
Proposition. There is one infinite distinct-singleton system whose
delayed excluded union B, full Haar union measure β, and
increasing-order first-kill masses eq satisfy
Its survivor set has natural density 1−β>3/4, so this is
not a counterexample to Problem 25. It rules out bounded additive
amortization even for one fixed family of finite total energy; it does
not rule out the required o(logX) bound.
The finite input is the proved construction (1): for some absolute
C∗, every T>0 admits a finite singleton family
F, all of whose moduli are at most a cutoff X, with
E(F)≤C∗,DF(X):=HBF(X)−βFHX>T.(28)
Only this established finite input is needed below.
The exact affine lift
Let an already installed finite system have full union Uold
of measure less than one and common period P. Choose a surviving
residue b∈[0,P), and let L be a multiple of P.
Replace every class a(modq) in a fresh finite family by
La+b(modLq).(29)
This residue is normalized, and the lifted full union lies in
[b]L, hence avoids Uold. Its actual delayed union is
exactly LBF+b: since 0≤b<L, the inequality
Ln+b≥Lq is equivalent to n≥q.
The lifted footprint is βF/L. If all lifted
moduli follow the old ones, its first-kill masses are eq/L,
so its energy contribution is
Suppose the first j−1 blocks and increasing cutoffs Yi
have been chosen. Their finite delayed union B<j, of footprint
β<j, has a bounded harmonic discrepancy: for a finite
constant Cj−1,
HB<j(N)−β<jHN≥−Cj−1(N≥1).(32)
This follows from periodic partial summation and the finitely many
activation exceptions. Use C0=0 for the empty prefix.
Choose Lj, a multiple of the old period, sufficiently large that
The old footprint is below 1/4, so an old surviving residue
bj exists. Apply (28) with
DFj(Xj)>Lj(j+Cj−1+3)+logLj+2,
lift by (29), and put Yj=LjXj+bj.
Each new modulus is at least Lj>Yj−1, whereas all old
moduli are at most Yj−1. Thus the global moduli are distinct
and strictly ordered block by block. Their full block unions are
disjoint. Equations (31)--(32) give
Finally, the whole delayed block j lies in
{Ljn+bj:n≥1}, with at most N/Lj points below
N. Hence
∣(B∖B≤J)∩[1,N]∣≤Nj>J∑Lj−1.
Finite-prefix periodicity and this summable tail prove d(B)=β.
This completes (27), including original activation and natural-density
existence. Preparations can thus be repeated with summable density and
energy cost while producing indefinitely increasing additive spikes.
Only a normalized, sublogarithmic estimate could settle the original
problem; the present construction neither supplies nor refutes it.