Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


These arguments are Plasma AI's author-recorded mathematics, without independent review. The specified failed extension has a complete proof; proposed repairs and asymptotic heuristics below are explicitly separate.

The relaxation and what its zeros force

Let R4(N,k)R_4(N,k) consist of linear functionals E~\widetilde{\mathbb E} on polynomials of degree at most four in z0,…,zN−1z_0,\ldots,z_{N-1}, reduced using zi2=ziz_i^2=z_i, such that:

  1. E~1=1\widetilde{\mathbb E}1=1 and E~[(∑izi−k)m]=0\widetilde{\mathbb E}[(\sum_i z_i-k)m]=0 for every monomial mm of degree at most three;
  2. E~p2≥0\widetilde{\mathbb E}p^2\ge0 for every polynomial pp of degree at most two;
  3. E~zS=0\widetilde{\mathbb E}z_S=0 whenever ∣S∣≤4|S|\le4 and SS is not a strong Sidon set. This includes every three-term progression and every four-point collision of two pair sums.

A Sidon kk-set gives such a functional by evaluation. Put Pd=∑i=0N−1−dzizi+dP_d=\sum_{i=0}^{N-1-d}z_i z_{i+d}, and let QtQ_t count unordered pairs of sum tt, with zt/2z_{t/2} for a diagonal pair when that index exists. Every off-diagonal term of Pd2P_d^2 has forbidden support, so

E~Pd2=E~Pd=pd,E~(Pd−pd)2=pd(1−pd).\widetilde{\mathbb E}P_d^2=\widetilde{\mathbb E}P_d=p_d, \qquad \widetilde{\mathbb E}(P_d-p_d)^2=p_d(1-p_d).

Positivity implies 0≤pd≤10\le p_d\le1, and the same argument applies to QtQ_t. Thus the degree-two moments lie in the relaxation R(N,k)R(N,k) of the linear-capacity account. For example, its pair-literal inequalities follow by squaring zizjz_i z_j, zi(1−zj)z_i(1-z_j) and (1−zi)(1−zj)(1-z_i)(1-z_j).

A genuine probability measure on kk-sets satisfying the zeros is supported on Sidon sets. Consequently a genuine witness at these parameters would be an actual construction, not merely a relaxation obstruction. To establish a barrier without constructing such sets, one needs a functional which is not a probability measure. It remains open whether R4(N,k)R_4(N,k) is nonempty at k=N+cN1/4k=\sqrt N+cN^{1/4} for some fixed c>0c>0 along an unbounded sequence.

A precise failed extension

L216's equal-block law has ss blocks of length W=s3−s2+sW=s^3-s^2+s, with ss points per block, followed by a uniform rotation. Thus N=sWN=sW and k=s2k=s^2. Let p(S)p(S) denote its inclusion moments. Zero every non-Sidon moment of degrees three and four, and multiply each surviving degree-tt moment by

at=(kt)∑∣S∣=t, S Sidonp(S)(t=3,4).a_t=\frac{\binom kt}{\sum_{|S|=t,\ S\text{ Sidon}}p(S)} \quad(t=3,4).

Leave degrees zero, one and two unchanged. This restores the total moment of each degree exactly; it does not claim to restore every local cardinality identity.

L217 proves this functional fails positivity for all sufficiently large s. For the short-pair polynomial H=∑d<WPdH=\sum_{d<W}P_d it gives

L((H−EH)2)≤−9−2212s3+O(s5/2)<0.\mathcal L((H-\mathbb E H)^2) \le-\frac{9-2\sqrt2}{12}s^3+O(s^{5/2})<0.

The mechanism is quantitative. The original variance is at most (3+22)s3/12+O(s5/2)(3+2\sqrt2)s^3/12+O(s^{5/2}), whereas the mass of repeated short differences is s3+O(s2)s^3+O(s^2). Zeroing removes that mass and possibly more. The factors at=1+O(s−4)a_t=1+O(s^{-4}) restore only O(s2)O(s^2) in this square. The claim's evidence also evaluates the entire functional exactly at N=63N=63, where the centered square is −941730900101847658/109020148158776379-941730900101847658/109020148158776379.

Any repair of the zeroed law which keeps its first two moments must add Ω(s3)\Omega(s^3) to this short-pair square. Uniform degreewise renormalization cannot do that. A nonuniform repair is not excluded: the total fourth-moment mass available to redistribute is larger, and the challenge is its consistency across pairings, zeros, cardinality identities and all positive-semidefinite blocks.

The claim also excludes adding a uniform random-kk-set component before zeroing, throughout the corresponding family with any fixed positive excess coefficient. Write W=s3−βs2+O(s)W=s^3-\beta s^2+O(s), N=sWN=sW, k=s2k=s^2, 0<β≤10<\beta\le1, and let the uniform component have weight αs\alpha_s. Difference one forces αs≤1−β+O(s−1)\alpha_s\le1-\beta+O(s^{-1}). The cyclic statistic

F=∑d<W(dW−13)(Pd+PN−d)F=\sum_{d<W}\left(\frac dW-\frac13\right)(P_d+P_{N-d})

has genuine variances 19s3/270+o(s3)19s^3/270+o(s^3) under the block law and s3/9+o(s3)s^3/9+o(s^3) under the uniform law. Their means differ by only O(s)O(s). Ordinary Sidon zeroing removes s3/9+o(s3)s^3/9+o(s^3) from its square; signed collision terms of other kinds and the uniform renormalization cost only o(s3)o(s^3). Thus the repaired centered square is −11(1−αs)s3/270+o(s3)-11(1-\alpha_s)s^3/270+o(s^3), which is negative for all sufficiently large ss. The proof counts the signed terms and handles the cyclic edges crossing the interval boundary explicitly. A large variance of the unweighted short-pair count after mixing therefore does not repair the whole matrix.

This last statement is asymptotic. At the small capacity-feasible mixture N=63N=63, k=9k=9, α=33/82\alpha=33/82, the signed cyclic square is positive, even though the unweighted short-pair square is negative. Both values are checked exactly in the claim's evidence. No all-size assertion is inferred from the asymptotic calculation.

An independent-displacement lattice gives a related exploratory signal. In the parameters N=4000N=4000, k=65k=65, displacement width 265265 and short-distance cutoff 398398, its sampled short-pair variance is much smaller than its sampled repeated-difference mass. That simulation uses labeled positions and permits coincidences; it does not evaluate a fully specified repaired functional and is not a proof of its failure. The exact block-law theorem supplies the rigorous obstruction above.

Full cyclic symmetry cannot be retained

For odd NN, a cyclically translation-invariant member of R4(N,k)R_4(N,k) would satisfy

k(k−1)≤N−1.(1)k(k-1)\le N-1. \tag{1}

To see this, every nontrivial modular collision of two unordered sums can be rotated to an ordinary collision. For four distinct points, track the integer difference of the two sums under every rotation. It is a multiple of NN, has average zero, and changes by at most NN at a step, since at most one of the four distinct points wraps. It therefore takes the value zero. For three points forming a modular progression, take its step in {1,…,(N−1)/2}\{1,\ldots,(N-1)/2\}, reversing its sign if necessary, and rotate the center to that step: the points become 0,d,2d0,d,2d. For odd NN, a modular collision 2a=2b2a=2b is trivial. These are all cases.

Translation invariance propagates each ordinary zero to its entire orbit, so all modular collision moments vanish. The cyclic difference count Cd=∑i∈ZNzizi+dC_d=\sum_{i\in\mathbb Z_N}z_i z_{i+d} then satisfies E~Cd2=E~Cd\widetilde{\mathbb E}C_d^2=\widetilde{\mathbb E}C_d, and hence has mean at most one. Summing over d≠0d\ne0 gives (1) by the cardinality identities. The oddness assumption avoids the two-point antipodal collision.

For odd NN with k(k−1)>N−1k(k-1)>N-1, a degree-four extension of the translation-invariant second moments in L216 must break that symmetry at a higher degree. Averaging an arbitrary ordinary-Sidon functional over all cyclic rotations does not preserve its ordinary zeros, so symmetry reduction is not legitimate here.

The pair-count covariance block

Every feasible functional has a positive-semidefinite matrix

C(d,e)=E~(Pd−pd)(Pe−pe),C(d,d)=pd(1−pd).C(d,e)=\widetilde{\mathbb E}(P_d-p_d)(P_e-p_e),\qquad C(d,d)=p_d(1-p_d).

For the narrower degree-two tent of the linear-capacity note, with w=k2−Nw=k^2-N and λ=(1+θ)/N2\lambda=(1+\theta)/N^2, the exact formula for d<wd<w is

1−pd=d2N2+θ(w−d)(N−d)N2.(2)1-p_d=\frac{d^2}{N^2} +\theta\frac{(w-d)(N-d)}{N^2}. \tag{2}

At k=N+cN1/4k=\sqrt N+cN^{1/4}, θ=(4c2)−1−1+o(1)\theta=(4c^2)^{-1}-1+o(1). When θ=0\theta=0, any proposed extension with ∣C(d,2d)∣≍N−1/2|C(d,2d)|\asymp N^{-1/2} for d=o(N3/4)d=o(N^{3/4}) violates the 2×22\times2 principal minor, since its diagonal product is O(d4/N4)=o(N−1)O(d^4/N^4)=o(N^{-1}). An incompletely factorized moment rule can produce just such a term by mishandling the shared-point progressions. This is a conditional diagnostic, not a claim that all extensions have this covariance. At fixed positive θ\theta, the larger diagonal slack in (2) removes that particular contradiction; L217 identifies a collective obstruction instead.

For odd NN, the complementary cyclic classes have means pd+pN−dp_d+p_{N-d}, 1≤d≤(N−1)/21\le d\le(N-1)/2. Their total excess over one per class is

(k2)−N−12=k2−N−k+12.\binom k2-\frac{N-1}{2}=\frac{k^2-N-k+1}{2}.

A perfect cyclic difference set has the pointwise relation Pd+PN−d=1P_d+P_{N-d}=1. That relation does not make covariances between different classes zero: they can share dependence on the cut. A general ordinary-Sidon functional need not have the complementary relation at all. A construction must allocate its covariance consistently, rather than infer independence from this example.

Which four-point configurations are erased

For distinct positive d,ed,e, consider the four distinct positions {0,d,t,t+e}\{0,d,t,t+e\}. They contain an ordinary nontrivial sum collision precisely when t=(d−e)/2t=(d-e)/2, or when a three-term progression occurs. The latter gives

t∈{2d,−d,d/2, 2d−e,−d−e,d/2−e,−2e,e,−e/2, d−2e,d+e,d−e/2}.\begin{split} t\in\{&2d,-d,d/2,\ 2d-e,-d-e,d/2-e,\\ &-2e,e,-e/2,\ d-2e,d+e,d-e/2\}. \end{split}

Half-integral offsets are omitted; duplicate offsets and coinciding positions must be treated only once. These are obtained by inspecting each of the four triples. At generic short distances, each offset has about NN translates, so their contributions to a pair-count covariance have scale 1/N1/N when four-point moments have scale N−2N^{-2}. Summing across many distances can therefore matter even if each individual entry is small. This list is a counting aid, not a positive-semidefinite completion.

A nonuniform repair and its unresolved compatibility

A four-point moment appears in three pairings. A correction specified only for one pairing may be inconsistent with the other two. One symmetric candidate, for a short-range kernel KK, is proportional to

K(a,b)K(c,e)+K(a,c)K(b,e)+K(a,e)K(b,c).(3)K(a,b)K(c,e)+K(a,c)K(b,e)+K(a,e)K(b,c). \tag{3}

If KK is positive semidefinite, the unrestricted Gaussian pairing tensor has a positive-semidefinite pair matrix. This fact does not establish positivity after deleting forbidden entries, fixing repeated-index moments by the Boolean relations, or enforcing the local cardinality identities. A correction of size N−2/WN^{-2}/W on configurations with two short pairs can contribute order WW to H2H^2, the scale demanded by L217; a uniform correction of size N−3N^{-3} contributes only order W2/NW^2/N. This is a scale calculation, not a construction.

The principal open test is to perform the three modifications in (3) and control every moment-matrix direction, including the low spatial frequencies where the block law has very small variance. Repairing only the constant short-pair direction does not suffice. A useful alternative is a signed combination of genuine Sidon laws: its zeros hold componentwise, but its positivity and fixed-cardinality identities remain new obligations. Continuing Singer-cut moments past their genuine arc-count range is one proposed family; no such positive continuation is constructed here.

An upper-bound attack could instead show that every admissible correction must fail in some direction, with a bound uniform in NN and kk. Neither L217 nor the symmetry obstruction establishes that stronger statement.

The parity obstruction adds a stronger test of these moment rules for even block length. In the stated scale domain, the alternating count ∑d(−1)dPd=(B2−Z)/2\sum_d(-1)^dP_d=(B^2-Z)/2 has negative square expectation after zeroing, with or without uniform renormalization, for every mixture weight once k−Nk-\sqrt N exceeds an absolute constant. Its necessary parity budget applies to all corrections that keep the first two moments.

Product kernels on even shifts can protect that statistic conditionally. Their local construction is unresolved: the progression-extension example defeats the proposed contracting-error bound used to enforce every Sidon zero. The cardinality lift survives, and the exact genuine short-count covariance provides a concrete input for later positivity estimates.

L274 supplies a different global signed completion for N≥55N\ge55, with every Sidon zero and local cardinality identity and the first two moments unchanged. For N≥58N\ge58 a finite Sidon-supported trade also restores the alternating square. It proves linear realizability and identifies the exact compatible subspace; the square local-kernel matrix is singular because it ignores the forbidden-triple relations. Full matrix positivity and the control needed for a localized version remain open.