Wiki
Wiki

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

Updated

Dilation memory and the collision attack


This calculation examines Section 3 of the preserved source, in the positive-mark case ℓ≥1\ell\ge1 consumed by P. Source mathematics is attributed to OpenAI; the independent examination and its derivations are prepared for Plasma AI. The notation BmemB_{\rm mem} below distinguishes the memory cutoff from the endpoint discrepancy exponent. All parameters other than xx are fixed in the order specified in the report.

A prime pays for one residue, not for every return

Fix an expanded path of NN edges, with offsets hih_i and active label sets Λi\Lambda_i at its N+1N+1 visits. Put q0=qN=qq_0=q_N=\sqrt q, qi=qq_i=q at the other visits, and ηi=1−qi\eta_i=1-q_i.

For a prime pp that is active, compatibility requires all active offsets to have one residue cc modulo pp. Conditioning the root on that residue has probability 1/p1/p. If a,za,z are its first and last active visits, its remaining factor is

1p∏i: p∉Λi(1−ηi1hi≡c(modp)).(M1)\frac1p\prod_{i:\,p\notin\Lambda_i} (1-\eta_i\mathbf1_{h_i\equiv c\pmod p}). \tag{M1}

Expand the product before aa by its earliest selected index and the product after zz by its latest selected index. Equivalently, subtract successive partial products. A chosen earlier or later endpoint contributes −ηi-\eta_i and requires the same residue cc; intervening inactive hits contribute qiq_i. There is no condition outside the resulting interval.

For a never-active prime, expand its entire product and group every subset of size at least two by its first and last indices. The empty and singleton subsets contribute

bp=1−1p∑iηi.b_p=1-\frac1p\sum_i\eta_i.

The contribution with endpoints j<ij<i is

ηjηip 1hj≡hi(modp)∏j<t<i(1−ηt1ht≡hj(modp)).(M2)\frac{\eta_j\eta_i}{p}\, \mathbf1_{h_j\equiv h_i\pmod p} \prod_{j<t<i}(1-\eta_t\mathbf1_{h_t\equiv h_j\pmod p}). \tag{M2}

Thus, after extracting ∏p bigbp\prod_{p\ {\rm big}}b_p, each represented prime has one interval of existence, possibly with no active visit. Repeated inactive hits are retained in its product; they are not independent draws. For large xx, p≥P∗:=exp⁡(Lc)≫Np\ge P_*:=\exp(L^c)\gg N, so bp>0b_p>0.

In a physical path, a prime active on both ends of an edge divides kDkD. All group primes exceed ∣k∣|k|. The free-label ban and the distinctness of each physical list force that prime to be one of the prescribed shared labels. A prime entering or leaving unshared cannot divide DD. Hence each maximal active run has exactly one factor Vg−1V_g^{-1}. A prime with rr active runs therefore has required total factor

Vg−rpbp.(M3)\frac{V_g^{-r}}{p b_p}. \tag{M3}

This argument is unchanged for negative kk.

Use νg(p)=(Vgpbp)−1\nu_g(p)=(V_g p b_p)^{-1} for an active birth and λg(p,r)=νg(p)\lambda_g(p,r)=\nu_g(p) with counting measure on residues. An active birth followed by r−1r-1 promotions supplies (M3). A ghost birth supplies Vgνg(p)V_g\nu_g(p) and rr promotions supply Vg−rV_g^{-r}, again giving (M3). Prescribing a later zero residue costs one point of counting measure, not another 1/p1/p.

Choose ρ\rho with q<ρ2<1\sqrt q<\rho^2<1. At an inactive internal hit the incoming edge, visit, and outgoing edge give ρ(qi/ρ2)ρ=qi\rho(q_i/\rho^2)\rho=q_i. A ghost endpoint gives ρ(−ηi/ρ)=−ηi\rho(-\eta_i/\rho)=-\eta_i in the appropriate order. Promotion precedes the visit operation and storage follows it, so active visits acquire none of these inactive-hit factors. Empty initial and terminal memories account for the boundary visits with q0=qN=qq_0=q_N=\sqrt q.

Under distinct birth values, the active visits and the two optional ghost endpoints determine every storage, promotion, and death. Conversely these operations recover precisely one term of (M1) or (M2). The 1/b!1/b! for an unordered ghost batch removes its orderings. This establishes the exact memory identity rather than a probabilistic analogy.

Factorial adjoints, including numerical coincidences

Consider a ghost operation in one group. Write A=qi/ρ2A=q_i/\rho^2, D=−ηi/ρD=-\eta_i/\rho, and C=VgDC=V_gD. Suppose a row deletes tt zero particles, keeps kk, and creates bb. In its inner product the factorial measure and deletion choice combine as

1(k+t)!(k+tt)1b!=1k!t!b!.(M4)\frac1{(k+t)!}\binom{k+t}{t}\frac1{b!} =\frac1{k!t!b!}. \tag{M4}

The joint integral consequently has factor Az(u)DtCbA^{z(u)}D^tC^b against λgkνgtνgb\lambda_g^k\nu_g^t\nu_g^b. Swapping the deleted and created variables proves that the adjoint interchanges C,DC,D. No reciprocal-prime factor appears. This remains true on numerical diagonals: selections are of particle indices, and symmetric integration retains their multiplicities.

For the Schur weight w=vjw=v^j, the absolute row ratio is

exp⁡(∣C∣vνg(Pg))(A+∣D∣/v)z,(M5)\exp(|C|v\nu_g(\mathcal P_g)) (A+|D|/v)^{z}, \tag{M5}

and the column ratio interchanges C,DC,D. Choose fixed vv sufficiently large that

qiρ2+2max⁡(1,v+)ηiρv<1\frac{q_i}{\rho^2}+ \frac{2\max(1,v_+)\eta_i}{\rho v}<1

for both possible qiq_i. This also covers doubling every ghost-birth coefficient. Since νg(Pg)=1+O(N/P∗)\nu_g(\mathcal P_g)=1+O(N/P_*), the cost is a constant per group, hence LCvL^{C_v} overall. Crucially, CvC_v does not depend on JJ, the probes, or the comparison coefficient exponent.

For an edge, let aa target slots be promoted from memory and bb source slots be stored. If the input memory has size jj, selecting its ordered promotion indices leaves measure

(j)aj!=1(j−a)!=(j−a+b)b(j−a+b)!.(M6)\frac{(j)_a}{j!}=\frac1{(j-a)!} =\frac{(j-a+b)_b}{(j-a+b)!}. \tag{M6}

The second expression is the reversed retrieval of the original stores. The old residues of promoted particles are −Δ-\Delta and the new residues of stored particles are Δ\Delta, where Δ=±kD\Delta=\pm kD. They are nonzero because these particles cannot divide DD. Translation preserves counting measure. In the reversed row convention the additional scalar is Vgb−aV_g^{b-a}, bounded per group because a,b≤ℓ+ma,b\le\ell+m.

The number of ordered promotions from zz eligible pending particles is controlled together with their unused output damping:

(z)aρz−a≤sup⁡t≥a(t)aρt−a<∞.(M7)(z)_a\rho^{z-a}\le \sup_{t\ge a}(t)_a\rho^{t-a}<\infty. \tag{M7}

Storage choices, the factors vb−aVg−av^{b-a}V_g^{-a}, and fresh integrations have bounded cost per group. Reversal gives the column estimate. Thus the absolute edge bounds are LCaL^{C_a}, with CaC_a independent of JJ. Arbitrary local multipliers of modulus at most one preserve these bounds.

Set Bmem=⌈L2⌉B_{\rm mem}=\lceil L^2\rceil. At most (ℓ+m)∣B∣N(\ell+m)|\mathcal B|N particles can enter memory by storage. Exceeding the cutoff therefore requires at least Bmem−O((ℓ+m)sN)B_{\rm mem}-O((\ell+m)sN) ghost births. Doubling those births in the absolute evolution gives an omitted mass at most

2−Bmem+O((ℓ+m)sN)LO(N)=exp⁡(−Ω(L2)).(M8)2^{-B_{\rm mem}+O((\ell+m)sN)}L^{O(N)} =\exp(-\Omega(L^2)). \tag{M8}

The initial and terminal empty-memory vectors have bounded norm. For the small part this is the normalized distinct-list harmonic sum, at most one; for the big part it is ∏gνg(Pg)M=1+o(1)\prod_g\nu_g(\mathcal P_g)^M=1+o(1).

Why dirty edges are rare and clean edges use the ideal norm

Fix a source state, all big choices, and the free labels. In each small group the source symmetrization omits a uniform ℓ\ell-subset of its MM distinct primes. If FF is the full small-label product and UU the omitted product, the small part of the step is F/UF/U. There are

D=(J+ℓℓ)∣S∣\mathcal D=\binom{J+\ell}{\ell}^{|\mathcal S|}

distinct possible positive integers UU, each at most exp⁡(O(TLb))<P∗\exp(O(TL^b))<P_*. For an eligible pending particle (p,r)(p,r),

r±kDBF/U≡0(modp)(M9)r\pm kD_{\mathcal B}F/U\equiv0\pmod p \tag{M9}

has at most one of these solutions: its nonzero factors are units modulo pp, and the UU are distinct modulo pp. If r=0r=0 there is no solution. At most BmemB_{\rm mem} omission choices can enable any promotion. The coefficient depends only on big labels, so conditioning has not biased the small omission law. Combining the improved row bound with the unrestricted column bound gives LCaBmem/DL^{C_a}\sqrt{B_{\rm mem}/\mathcal D}. Reversal applies the same argument to stores. The total dirty norm is at most twice that quantity.

On a clean edge no particle enters or leaves memory. Absorb the two pending-zero damping multipliers and memory projections into the endpoint test vectors. They are contractions and commute with active-list symmetrization. Fix the JJ shared labels in each small group. Summing the remaining ℓ\ell small slots with half of the joint normalization at each endpoint gives maps PdP_{\mathbf d} satisfying

∑d∥Pdw∥2≤LCs∥w∥2.(M10)\sum_{\mathbf d}\|P_{\mathbf d}w\|^2 \le L^{C_s}\|w\|^2. \tag{M10}

To check the exponent, the one-group multiplier relative to the original state measure is bounded by

sup⁡z≥Mqz−M(z−M+ℓ)ℓ/Vgℓ,\sup_{z\ge M}q^{z-M} (z-M+\ell)_\ell/V_g^\ell,

a constant independent of JJ and of the comparison family. Fourier transformation on the unrestricted small residues and the pending residues turns translation into e(±ΘDB)e(\pm\Theta D_{\mathcal B}). Fixing pending prime lists makes Θ\Theta independent of the active big labels, including when an active value happens to equal a pending one.

The remaining big-label operator is the ideal operator or its adjoint. Changing μg\mu_g to νg\nu_g changes its norm by at most OJ(LC1sN/P∗)O_J(L^{C_1}sN/P_*) under the square-root-density identification. Forbidding free/active coincidences costs at most OJ,m(LC1s/P∗)O_{J,m}(L^{C_1}s/P_*) by row and column estimates: a free draw has atom O(P∗−1)O(P_*^{-1}) and there are only OJ,m(s)O_{J,m}(s) relevant comparisons. Both errors beat every fixed negative logarithmic power. Together with (M10), the clean norm is at most 2L−Eid+Cs2L^{-E_{\rm id}+C_s}.

Choose G>E+Cv+3G>E+C_v+3 and Eid>G+Cs+2E_{\rm id}>G+C_s+2 first. After the comparison family has fixed CaC_a, choose JJ so that

c02log⁡(J+ℓℓ)>Ca+G+3.\frac{c_0}{2}\log\binom{J+\ell}{\ell}>C_a+G+3.

Then each signed truncated edge has norm at most L−GL^{-G}. The exponents that determine the ideal target do not depend on the later choice of JJ.

Strongest collision attack

A single absolute collision estimate would fail. Its factor P∗−1P_*^{-1} would have to absorb a possible LCNL^{CN} absolute path cost, whereas log⁡P∗=Lc=o(Nlog⁡L)\log P_*=L^c=o(N\log L). This remains a threat when an early prime is dropped and a much later fresh birth is forced to equal it: the ordinary state no longer remembers the early value.

Let potential birth addresses include initial slots, fresh target slots, and ordered ghost-batch coordinates. There are A∗=LO(1)A_*=L^{O(1)} addresses under the memory cutoff. For disjoint blocks of addresses of size at least two, assign coefficient ∏B(−1)∣B∣−1(∣B∣−1)!\prod_B(-1)^{|B|-1}(|B|-1)! and require all their addresses to occur and to have equal values within each block. The signed sum is exactly the distinctness indicator. Indeed it is the sign sum of permutations preserving each numerical-value class, which vanishes on a class of size at least two by multiplication by a transposition.

If r=∑B(∣B∣−1)r=\sum_B(|B|-1), there are at most 2r2r affected addresses, and the total absolute coefficient at rank rr is at most A∗2rA_*^{2r}. This follows, for example, by taking the coefficient of trt^r in ∏j=0A∗−1(1+jt)\prod_{j=0}^{A_*-1}(1+jt) and bounding it by (∑jj)r/r!(\sum_jj)^r/r!.

For large rank, condition on the chronologically first value in each block. Every subsequent constrained birth is a genuinely fresh integration with atom O(P∗−1)O(P_*^{-1}). In an edge its step and promotion choices were already fixed before fresh target values were integrated. In a ghost operation the ordered batch still has its factorial divisor. Retaining pivot values in the conditioning even after their particles die allows backward induction using the uniform row bounds. The fixed-block contribution is bounded by

LCh(N+1)(C/P∗)r.(M11)L^{C_h(N+1)}(C/P_*)^r. \tag{M11}

For small rank, encode an equality with a dead pivot at its two births:

1p1=p0=∫01e(tp1)e(−tp0) dt.(M12)\mathbf1_{p_1=p_0}= \int_0^1 e(t p_1)e(-t p_0)\,dt. \tag{M12}

No value must then travel in the state after the pivot dies. For a larger block use one such phase for each nonpivot. At fixed Fourier parameters, only the birth operations in that block change. At most 2r2r edges lose their signed estimate; all other edges keep their whole pattern sum and symmetrizations. Initial-birth phases preserve the boundary norm. An ordered ghost-batch multiplier can be averaged over its permutations, since the remaining integrand is symmetric; its modulus stays at most one and (M4) still supplies its adjoint bound. Thus this route gives

O(L(−G+Cv)N+Cv+2r(G+Ca)).(M13)O\left(L^{(-G+C_v)N+C_v+2r(G+C_a)}\right). \tag{M13}

Split the rank sum at r0=⌈C′′Nlog⁡L/Lc⌉r_0=\lceil C''N\log L/L^c\rceil. Summing (M11) with the coefficient bound gives o(L−EN)o(L^{-EN}) when C′′C'' is large enough. Since r0/N=o(1)r_0/N=o(1), summing (M13) below r0r_0 gives L(−G+Cv+o(1))N=o(L−EN)L^{(-G+C_v+o(1))N}=o(L^{-EN}). This defeats the dead-pivot attack without replacing signed contraction by one absolute collision estimate.

Return to integer roots and endpoint pairings

The product of distinct active primes has logarithm OJ(NTLd)=o(L)O_J(NTL^d)=o(L) because 0.52+d<10.52+d<1. Factor out all deterministic damping belonging to these primes before approximating any average. For the remaining primes write the damping as ∏p(1−Xp)\prod_p(1-X_p) with 0≤Xp≤10\le X_p\le1. The sum of independent expectations is O(NT)O(NT). Consecutive Bonferroni truncations at degree h≍NTh\asymp NT have expectation gap at most λh/h!\lambda^h/h!. Choosing its constant large yields any required exp⁡(−ANT)\exp(-A NT) relative precision.

The number of residue terms is exp⁡(O(h(Ld+log⁡N+log⁡s)))=exp⁡(o(L))\exp(O(h(L^d+\log N+\log s)))=\exp(o(L)). Their CRT counting errors on [X,2X)[X,2X), X≥xγX\ge x^\gamma, total exp⁡(−γL+o(L))\exp(-\gamma L+o(L)), negligible relative to Qact−1exp⁡(−O(NT))Q_{\rm act}^{-1}\exp(-O(NT)). The possibly much smaller deterministic damping has already been factored identically in the two models. Absolute path mass is LO(N)L^{O(N)} by the physical row bound and initial normalized list mass at most one, so the relative errors can be summed. The exact return condition is the integral of e(θhN)e(\theta h_N) over [0,1][0,1]. Restoring this condition, the memory tail, and the residue error gives the root moment used in Theorem 3.5.

Finally, set B0=AA∗B_0=\mathcal A\mathcal A^*. On a position block IjI_j of length comparable to the maximum step HH, the matrix Gnm=⟨un,B0Rum⟩G_{nm}=\langle u_n,B_0^Ru_m\rangle is positive semidefinite. Its largest eigenvalue is at most its trace. Mark independence gives fj=∑n∈Ijfnunf_j=\sum_{n\in I_j}f_nu_n and hence

⟨fj,B0Rfj⟩≤(∑n∈Ij∣fn∣2)∑n∈Ij⟨un,B0Run⟩.(M14)\langle f_j,B_0^Rf_j\rangle \le \Bigl(\sum_{n\in I_j}|f_n|^2\Bigr) \sum_{n\in I_j}\langle u_n,B_0^Ru_n\rangle. \tag{M14}

This uses the coefficient norm in the unu_n expansion; it does not assume equal norms for the unu_n. Spectral Hölder bounds the pairing by ∥gj∥∥fj∥1−1/R\|g_j\|\|f_j\|^{1-1/R} times the 1/(2R)1/(2R) power of (M14). Since log⁡H=OJ(TLd)\log H=O_J(TL^d) and sup⁡∣fn∣≤exp⁡(O(L))\sup|f_n|\le\exp(O(\sqrt L)),

(O(H)sup⁡∣fn∣2)1/(2R)=O(1).(O(H)\sup|f_n|^2)^{1/(2R)}=O(1).

The HH-neighborhoods used to restrict gg have bounded overlap. Hölder over blocks with exponents 22, 2R/(R−1)2R/(R-1) and 2R2R, followed by the root moment, gives ∣⟨f,Ag⟩∣≪XL−E+2C3|\langle f,\mathcal Ag\rangle|\ll XL^{-E+2C_3}. The unnormalized mark fibers and either shift sign are therefore covered.

No computation or finite sampling is used in this derivation.