Wiki
Wiki

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

Updated


This is Plasma AI's author-recorded calculation, without independent review. It concerns the genuine, unrotated block law and does not construct Sidon pseudo-moments. Its role in the local-repair question is to identify the covariance terms that any proposed high-frequency estimate must control.

Take s≥2s\ge2 blocks of length W≥max⁡(s,4)W\ge\max(s,4), independently choosing a uniform ss-subset in each. Put N=sWN=sW and fj=(s)j/(W)jf_j=(s)_j/(W)_j for 1≤j≤41\le j\le4. For 1≤d<W1\le d<W, write Pd=∑bUb(d)+∑bVb(d)P_d=\sum_b U_b(d)+\sum_b V_b(d), where Ub(d)U_b(d) counts pairs at distance dd inside block bb, and Vb(d)V_b(d) counts those crossing from block bb to block b+1b+1. There are ss terms of the first kind and s−1s-1 of the second. Their means are ud=(W−d)f2u_d=(W-d)f_2 and vd=df12v_d=df_1^2.

For distinct d,e<Wd,e<W define

nde=2(W−max⁡(d,e))+2(W−d−e)+,rde=(e−d)++min⁡(W−d,e),tde=(d+e−W)+,Gde=((W−d)(W−e)−nde)f4+ndef3−udue,Hde=2min⁡(d,e)f1f2+(de−2min⁡(d,e))f22−vdve,Jde=f1{rdef2+((W−d)e−rde)f3}−udve,Qde=f12{tdef1+(de−tde)f2}−vdve.(1)\begin{split} n_{de}&=2(W-\max(d,e))+2(W-d-e)_+,\\ r_{de}&=(e-d)_++\min(W-d,e),\qquad t_{de}=(d+e-W)_+,\\ G_{de}&=((W-d)(W-e)-n_{de})f_4+n_{de}f_3-u_du_e,\\ H_{de}&=2\min(d,e)f_1f_2+(de-2\min(d,e))f_2^2-v_dv_e,\\ J_{de}&=f_1\{r_{de}f_2+((W-d)e-r_{de})f_3\}-u_dv_e,\\ Q_{de}&=f_1^2\{t_{de}f_1+(de-t_{de})f_2\}-v_dv_e. \end{split} \tag{1}

Then the covariance is exactly

C(d,e)=sGde+(s−1)Hde+2(s−1)(Jde+Jed)+(s−2)(Qde+Qed).(2)C(d,e)=sG_{de}+(s-1)H_{de} +2(s-1)(J_{de}+J_{ed})+(s-2)(Q_{de}+Q_{ed}). \tag{2}

For the diagonal use the same J,QJ,Q and replace G,HG,H by

Gdd=(W−d)f2+2(W−2d)+f3+((W−d)2−(W−d)−2(W−2d)+)f4−ud2,Hdd=df12+(d2−d)f22−vd2.(3)\begin{split} G_{dd}={}&(W-d)f_2+2(W-2d)_+f_3\\ &+((W-d)^2-(W-d)-2(W-2d)_+)f_4-u_d^2,\\ H_{dd}={}&df_1^2+(d^2-d)f_2^2-v_d^2. \tag{3} \end{split}

To verify (1), two internal edges of distinct lengths have a common vertex in nden_{de} placements: equal left or right endpoints contribute 2(W−max⁡(d,e))2(W-\max(d,e)), and a right endpoint equaling the other's left contributes 2(W−d−e)+2(W-d-e)_+. The other placements have four distinct points. Two edges crossing the same boundary have a common endpoint in 2min⁡(d,e)2\min(d,e) placements; their other placements use two points in each block. An internal dd-edge and a crossing ee-edge with an endpoint in its block share one of its vertices in rder_{de} placements. Finally two edges crossing adjacent boundaries have a common endpoint in tdet_{de} placements in their shared block. Subtract the product of means in each case. On the diagonal, identical edges give the extra terms in (3).

Independence eliminates all disjoint-block covariances. There are ss internal blocks, s−1s-1 boundaries, two sides of each boundary for an internal-crossing pair, and s−2s-2 adjacent boundary pairs. Including both orders gives (2). Reflection of a block makes the internal-crossing covariance identical on its two sides. This proves the formulas.

The two absolute-value terms

For d≠ed\ne e, expanding the maxima, minima and positive parts in (1) gives

C(d,e)=a0+a1(d+e)+a2de+KD∣d−e∣+KA∣d+e−W∣,(4)C(d,e)=a_0+a_1(d+e)+a_2de +K_D|d-e|+K_A|d+e-W|, \tag{4}

for constants a0,a1,a2a_0,a_1,a_2 depending only on s,Ws,W, with

KD=−s(f3−f4)−(s−1)(f1f2−f22)+2(s−1)f1(f2−f3),KA=s(f3−f4)−2(s−1)f1(f2−f3)+(s−2)f12(f1−f2).(5)\begin{split} K_D={}&-s(f_3-f_4)-(s-1)(f_1f_2-f_2^2) +2(s-1)f_1(f_2-f_3),\\ K_A={}& s(f_3-f_4)-2(s-1)f_1(f_2-f_3) +(s-2)f_1^2(f_1-f_2). \end{split} \tag{5}

For example, the coefficients of ∣d−e∣,∣d+e−W∣|d-e|,|d+e-W| in nden_{de} are −1,1-1,1; those in rde+redr_{de}+r_{ed} are 1,−11,-1. These give the first and third terms of (5); the other two contributions come directly from min⁡(d,e)\min(d,e) and tdet_{de}. Every remaining expression in (1) is a linear combination of 1,d+e,de1,d+e,de. Thus the polynomial part of the matrix has rank at most two, on the span of the constant and coordinate vectors. Equation (4) concerns off-diagonal entries; a diagonal correction from (3) remains.

If W=s3+O(s2)W=s^3+O(s^2), then

KD=s−6+O(s−7),KA=−s−6+O(s−7).(6)K_D=s^{-6}+O(s^{-7}),\qquad K_A=-s^{-6}+O(s^{-7}). \tag{6}

For a direct expansion, write y=s/W=s−2(1+O(s−1))y=s/W=s^{-2}(1+O(s^{-1})). Then f2=y2(1−s−1+O(s−3))f_2=y^2(1-s^{-1}+O(s^{-3})), f3=y3(1−3s−1+2s−2+O(s−3))f_3=y^3(1-3s^{-1}+2s^{-2}+O(s^{-3})) and f4=y4(1+O(s−1))f_4=y^4(1+O(s^{-1})). In KDK_D the terms of order sy3sy^3 cancel, leaving y3(1+O(s−1))+O(sy4)y^3(1+O(s^{-1}))+O(sy^4); in KAK_A they leave −y3(1+O(s−1))+O(sy4)-y^3(1+O(s^{-1}))+O(sy^4). This proves (6).

The negative effect of the first kernel has an exact finite-interval form. For real b1,…,bW−1b_1,\ldots,b_{W-1} with ∑dbd=0\sum_d b_d=0,

∑d,ebdbe∣d−e∣=−2∑r=1W−2(∑d≤rbd)2.(7)\sum_{d,e}b_db_e|d-e| =-2\sum_{r=1}^{W-2}\left(\sum_{d\le r}b_d\right)^2. \tag{7}

Express ∣d−e∣|d-e| as the number of cuts between dd and ee; each cut contributes 2(∑d≤rbd)(∑e>rbe)2(\sum_{d\le r}b_d)(\sum_{e>r}b_e), proving (7). The second kernel in (4) is the first composed with reflection e↦W−ee\mapsto W-e. Since reflection commutes with the first kernel, its quadratic form on the zero-sum subspace has absolute value at most the negative of (7), by Cauchy--Schwarz for the positive semidefinite form −∣d−e∣-|d-e| on that subspace.

Equations (4)--(7) make the interior spectral heuristic concrete. They do not give a high-frequency lower bound for the complete covariance after a Sidon repair. The diagonal, the polynomial part, the long differences, boundary conditions and the unconstructed correction must all be included in such a bound.

The research evidence entry point checks every mean and covariance against a separate complete enumeration of the unrotated sample space at (s,W)=(2,4),(3,4),(3,6),(4,6)(s,W)=(2,4),(3,4),(3,6),(4,6), in exact rational arithmetic. It also checks the two-kernel decomposition at every off-diagonal entry of these matrices. This is finite supplementary evidence; the general identities rest on the counting argument above.