ABC: source and evidence reader

Download original file

This is the original TeX manuscript source. Use the paper’s PDF for typeset equations.

Read the typeset paper

1 \section{Signed arithmetic COS and the sparse spectral leaf}\label{sec:sparse}
2 \subsection{What the finite assignment signal records}
3 The spectral branch of the project asks which prime assignments realize a prescribed residue. Its exact object is a finite distribution. Fix a finite abelian group $G$ and $s$ eligible variable support primes. At the $j$th prime choose one of three permitted contributions, represented by $0,\gamma_j,-\gamma_j$ in additive group notation. The sum of the chosen contributions is the assignment residue.
4 
5 Let $N(x)$ count assignments producing $x\in G$. Repeated contributions remain separate assignments, so
6 \[
7  M=\sum_{x\in G}N(x)=3^s,\qquad \mu(x)=N(x)/M.
8 \]
9 For a character $\chi\in\widehat G$, define
10 \[
11  \widehat\mu(\chi)=\sum_x\mu(x)\chi(x)
12  =\prod_{j=1}^s\frac{1+\chi(\gamma_j)+\chi(-\gamma_j)}3.
13 \]
14 On a cyclic channel $G=\Z/n\Z$, this becomes
15 \[
16  m(k)=\prod_{j=1}^s\frac{1+2\cos(2\pi k\gamma_j/n)}3.
17 \]
18 This is the discrete cosine or COS expression used in the project. It is an exact characteristic function. Individual cosine factors may be negative. No positivity of all Fourier samples is assumed.
19 
20 Character orthogonality gives the target count
21 \[
22  N(h)=\frac M{|G|}\sum_{\chi\in\widehat G}\widehat\mu(\chi)\overline{\chi(h)}.
23 \]
24 The identity is finite and exact. It solves a representation question after the arithmetic channel and admissible contributions have been specified. It does not by itself bound the height of an integer triple that generated that channel.
25 
26 \subsection{Sparsity forces transverse energy}
27 Let $E=\{x:N(x)>0\}$ and $r=|E|$. Always $r\le M$. Parseval yields
28 \[
29  \sum_{\chi\in\widehat G}|\widehat\mu(\chi)|^2
30  =\frac{|G|}{M^2}\sum_xN(x)^2.
31 \]
32 Cauchy--Schwarz on the occupied support gives $\sum_xN(x)^2\ge M^2/r$. Hence
33 \begin{proposition}[Sparse energy barrier]\label{prop:sparse-energy}
34 \[
35  \sum_{\chi\ne1}|\widehat\mu(\chi)|^2
36  \ge\frac{|G|}{r}-1\ge\frac{|G|}{M}-1.
37 \]
38 \end{proposition}
39 When few assignment atoms lie in a large group, substantial nontrivial Fourier energy is unavoidable. A failure of uniform mixing is therefore a structural feature of the signal, rather than evidence that the arithmetic assignment is invalid.
40 
41 \subsection{The hypothetical exception regime is sparse}
42 For a primitive triple put $Q=abc/R$. Suppose $c>R^{1+\eps}$ for a fixed $\eps>0$. Since $a,b$ are positive with sum $c$, one has $ab\ge c-1$. Thus, for large $c$,
43 \[
44  Q=\frac{abc}{R}\ge\frac{c(c-1)}R>\frac12R^{1+2\eps}.
45 \]
46 The unit group modulo $Q$ has order $\varphi(Q)$. For every $\delta>0$,
47 \[
48  \frac Q{\varphi(Q)}\ll_\delta R^\delta,
49  \qquad 3^{\omega(R)}\ll_\delta R^\delta.
50 \]
51 Both elementary bounds follow by separating a finite set of small primes. For all sufficiently large primes, $(1-1/p)^{-1}\le p^\delta$ and $3\le p^\delta$. Every prime dividing $Q$ also divides $R$.
52 
53 If the assignment model has $M=3^s$ with $s\le\omega(R)$, choose $\delta=\eps/2$ in both estimates. Then
54 \[
55  \frac{\varphi(Q)}M\gg_\eps R^{1+\eps}.
56 \]
57 Consequently a sufficiently large hypothetical exponent-gap exception, represented in this joint unit-group model, lies on the sparse side of the energy barrier. Uniform spectral mixing cannot be the universal finishing argument for this regime.
58 
59 The full unit group need not be cyclic. The preceding energy statement holds for any finite abelian group. The one-variable Prony argument below is specifically a theorem for a cyclic channel. It is not a claim that one character line automatically recovers all correlations in an arbitrary noncyclic product channel.
60 
61 \subsection{Exact innovation rank in a cyclic channel}
62 Let $G=\Z/n\Z$, $\alpha_x=e^{2\pi ix/n}$ and
63 \[
64  m(k)=\sum_{x\in E}\frac{N(x)}M\alpha_x^k.
65 \]
66 Form the shift matrix $S_d=(m(k+j))_{0\le k<n,\,0\le j\le d}$. It factors as a Fourier-column matrix times a Vandermonde matrix on the distinct occupied nodes. The Fourier columns are independent, and all weights $N(x)/M$ are nonzero. Therefore
67 \[
68  \boxed{\operatorname{rank}S_d=\min(r,d+1).}
69 \]
70 Before degree $r$, a small singular value is a conditioning phenomenon, not an exact reduction in the number of occupied residues.
71 
72 \begin{theorem}[Exact cyclic Prony reconstruction]\label{thm:prony}
73 The distribution on a cyclic channel with $r$ occupied residues is determined by the $2r$ exact consecutive samples $m(0),\ldots,m(2r-1)$.
74 \end{theorem}
75 \begin{proof}
76 Write
77 \[
78  A(z)=\prod_{x\in E}(z-\alpha_x)=z^r+\sum_{j=0}^{r-1}a_jz^j.
79 \]
80 For every $k$,
81 \[
82  \sum_{j=0}^{r-1}a_jm(k+j)=-m(k+r).
83 \]
84 The coefficient matrix for $0\le k<r$ is the Hankel matrix $H=(m(i+j))_{0\le i,j<r}$. With $V=(\alpha_x^i)_{i,x}$ and $D=\operatorname{diag}(N(x)/M)$, one has $H=VDV^{\mathsf T}$. The square Vandermonde $V$ is invertible and every diagonal entry of $D$ is nonzero. Thus $H$ is invertible, and the $2r$ samples determine the monic annihilator $A$.
85 
86 Its distinct roots identify the occupied nodes. The first $r$ sample equations then give an invertible Vandermonde system for their weights. Multiplication by the known $M$ recovers every multiplicity.
87 \end{proof}
88 This is an exact reconstruction theorem. It does not promise numerical stability from approximate samples. Nor does a subpolynomial number of samples by itself imply a subpolynomial arithmetic height for the reconstructed assignment.
89 
90 \subsection{Polynomial target filters and exact count certificates}
91 For a polynomial $P(z)=\sum_{j=0}^dc_jz^j$, define the collision quadratic form
92 \[
93  \mathcal E_d(P)=\frac n{M^2}\sum_{x\in E}N(x)^2|P(\alpha_x)|^2.
94 \]
95 It can be written as a positive semidefinite Gram form in the coefficients of $P$. Let
96 \[
97  \lambda_d(h)=\min\{\mathcal E_d(P):\deg P\le d,\ P(\alpha_h)=1\}.
98 \]
99 For every such filter, the target term is present with value $(n/M^2)N(h)^2$, so
100 \[
101  N(h)\le\frac M{\sqrt n}\sqrt{\lambda_d(h)}.
102 \]
103 If the right-hand side is rigorously less than one, the integer count is zero. An approximate decimal below one is not a certificate without a proved error enclosure.
104 
105 If $h$ is absent, a degree-$r$ polynomial vanishes at every occupied node and takes value one at $\alpha_h$, so $\lambda_r(h)=0$. If $h$ is occupied, its degree-$(r-1)$ Lagrange polynomial isolates exactly that node. Thus
106 \[
107  \lambda_{r-1}(h)=\frac n{M^2}N(h)^2.
108 \]
109 At the innovation degree the count bound is exact. The remaining computational issue is finding the needed filter with controlled exact coefficients and reliable arithmetic, rather than hoping for an unexplained asymptotic gain.
110 
111 \subsection{A Galois coordinate with a controlled denominator}
112 For an occupied target define
113 \[
114  \Delta_h(E)=\prod_{x\in E\setminus\{h\}}(\alpha_h-\alpha_x).
115 \]
116 This is a nonzero algebraic integer in $\Q(\zeta_n)$. For every unit $u$ modulo $n$, its conjugate is $\Delta_{uh}(uE)$. The absolute norm is a nonzero integer. Hence
117 \[
118  \prod_{u\in(\Z/n\Z)^\times}|\Delta_{uh}(uE)|\ge1.
119 \]
120 At least one factor is at least one. In that coordinate, the Lagrange numerator has coefficient $\ell^1$ norm at most $2^{r-1}$, and dividing by the target denominator preserves that upper bound.
121 
122 This removes a catastrophically small denominator in at least one complex coordinate. It does not supply a uniform radical-scale bound for every conjugate or for the arithmetic height. Even if $r=R^{o(1)}$, the quantity $2^r$ need not be $R^{o(1)}$.
123 
124 \subsection{What the spectral branch leaves open}
125 The valid endpoint is exact compression and extraction of a sparse arithmetic leaf. A further height theorem must exploit the arithmetic of that leaf, such as its simultaneous logarithmic, norm-form or $S$-unit constraints. The bounded representation count, exact innovation rank and finite Fourier identities do not prove the required inequality on $c/R$.

Back to source controls

Back to ABC: source and evidence reader