Sampling a growing carry table

An integral ignores the value assigned at a single point. A finite table records it. When the table and the function grow together, that one value can leave a discrepancy that survives averaging. For the carry table studied here, the discrepancy tends to one. Its source is a common reset of all the clocks representing the table. The proof must also account for the growing family of resets between them.

A digit collision asks whether two digit positions agree. Here the positions are the two digits of a base-$p$ word. In base three, the words $00$, $11$ and $22$ occupy the integer positions zero, four and eight. Place them on a circle with nine positions. Multiplication by two moves their marks to zero, eight and seven. A further step of two takes two marks across the join. Those crossings are the carries being counted.

For an odd prime base $p$, there are $p$ matching-digit words on a circle of $p^2$ positions. For each multiplier $a$ from zero through $p^2-1$, multiply their positions by $a$ and count the crossings under a further step of $a$. The resulting list of counts is the carry table. Subtracting the proportional allowance $a/p$ gives its centered readings. Their squares sum to the collision energy $E_p$.

The same table has a clock representation. Define the integer-zero sawtooth by $$\psi(x)=\begin{cases}\{x\}-\tfrac12,&x\notin\mathbb{Z},\\0,&x\in\mathbb{Z}, \end{cases} \qquad B_N(x)=2\sum_{j=1}^N\psi(jx),\qquad N=p-1,$$ where $\{x\}$ denotes the fractional part. Each component rises linearly and resets at multiples of $1/j$; this repeating motion is why we call it a clock. The clocks are added before the sum is squared, so their interactions are part of the energy.

The sampling grid consists of the $p^2$ points $0,1/p^2,\ldots,(p^2-1)/p^2$. Proposition 2.1 shows that the values of $B_N$ on this grid are the centered carry readings in a different order. The continuous capacity and the finite average are therefore $$\mathcal J(N)=\int_0^1B_N(x)^2\,dx,\qquad \frac{E_p}{p^2}=\frac1{p^2}\sum_{a=0}^{p^2-1}B_N(a/p^2)^2.$$ Their difference $\mathcal S_p=\mathcal J(p-1)-E_p/p^2$ is the sampling defect. Sampling here uses every entry of the carry table.

The Secondary Term in Digit-Collision Energy [7] proved that, for odd prime bases, $$E_p=p^3-\frac{p^2}{\pi^2}(\log p)^2 +O\!\left(\frac{p^2\log^2(2p)}{\log\log(3p)}\right).$$ That calculation bounded the sampling defect below the secondary scale and left its proposed limit $\mathcal S_p\to1$ open. The limit resolves a finer question about the same energy, with its exact continuous capacity retained.

The origin explains the candidate one. Each doubled clock approaches $-1$ just to its right and $+1$ just to its left around the periodic join. Thus $B_N^2$ approaches $N^2$ from either side, while $B_N(0)^2=0$. Replacing that single squared sample by $N^2$ raises the finite average by $N^2/p^2$, which tends to one. To prove that this is the entire limiting difference, we must control the combined signed discrepancy from the interior. Both the number of clocks and the sampling grid grow with $p$.

The proof gives an explicit positive power saving. Its exponent combines the derivative-estimate saving $1/(2^{14}-2)$ with a denominator cutoff at $p^{1/28}$, giving $$\eta=\frac{1}{28(2^{14}-2)}=\frac{1}{458696}.$$ These are conservative choices in the proof, explained at their points of use below. Their role is to establish convergence. The stronger square-root rate suggested by the numerical data is formulated in Conjecture 15.1.

In the original energy units, the unit defect is a quadratic correction. It lies inside the larger remainder of the secondary-term expansion. The theorem determines this correction relative to the exact capacity $\mathcal J(p-1)$; a finer expansion of that capacity is a separate question.

The sampling identity in Section 3 separates the origin from a signed sum of Dedekind terms. Reciprocity follows each term through division with remainders. An initial sequence of division steps is a prefix; its matrix records how the original pair is reconstructed from the smaller one. We stop when a remainder crosses a threshold and bound all the costs accumulated before that crossing. The terminal terms retain both possible orientations of the descent. Their signs allow them to be joined into a complete interval of primitive rational coordinates. Holding the numerator fixed then exposes reciprocal-phase oscillation in the denominator. This controls the terminal terms across all the original cutoffs and proves the limit.

The analytic ingredients are classical. We use Dedekind reciprocity and its cotangent representation [1], Weil’s complete Kloosterman bound including its Ramanujan zero mode [6], Erdős–Turán discrepancy [5], and the classical derivative estimate stated in [4]. The golden interval belongs to the geometry of signed continued fractions [3]; its population is proved directly below. Throughout the descent, the signed source, its cutoff and its multiplicity remain those of the original carry table.

Clock representation of the carry table

Fix an odd prime $p$ throughout, and write $$N=p-1,\quad q=p^2,\quad \ell=\log(2p),\quad \mathsf H_n=\sum_{j=1}^n\frac1j.$$ We write $(j,k)$ for the greatest common divisor. A bar over a unit denotes its inverse modulo the modulus in use. The integers from zero through $q-1$ represent all two-digit base-$p$ words, including leading zeros. This finite residue system is the two-digit carrier. The word with both digits equal to $d$ has value $pd+d$, so the equal-digit words occupy $G_p=\{(p+1)d:0\le d<p\}$. For $0\le a<q$ put $$C_p(a)=\sum_{n\in G_p} \left(\left\lfloor\frac{(n+1)a}{q}\right\rfloor -\left\lfloor\frac{na}{q}\right\rfloor\right), \qquad F_p(a)=C_p(a)-\frac ap,$$ and $E_p=\sum_{a=0}^{q-1}F_p(a)^2$. Each difference of floors is zero or one. It records whether the step from $na/q$ to $(n+1)a/q$ crosses an integer boundary, counting arrival at the boundary as a crossing. This is the circular carry test described above.

A step of $a$ crosses the join from exactly $a$ of the $q$ possible starting positions. The proportional allowance for the $p$ selected marks is therefore $pa/q=a/p$. Subtracting it defines $F_p$ without a random-digit assumption. The carry table is the list of $C_p(a)$; its centered table is the list of $F_p(a)$. These are the definitions used in [7].

Define the Dedekind sum for all integer $h$ and positive $k$ by $$s(h,k)=\sum_{a=1}^{k-1}\psi(a/k)\psi(ha/k),\qquad s(h,1)=0.$$ It is periodic and odd in $h$. On units it is invariant under inversion. We use the classical reciprocity identity $$s(h,k)+s(k,h)=\mathcal R(h,k),\qquad \mathcal R(h,k)=\frac{h^2+k^2+1-3hk}{12hk},\quad (h,k)=1.$$ These formulas use the integer-zero convention throughout [1].

Separating the common reset

At an interior reset, the jump in the squared profile depends on the readings of the clocks that do not reset there. The signed source below records their combined contribution to the sampling defect.

Put $M_k=\lfloor N/k\rfloor$, $s_k=N-kM_k$ and $$T_{k,s}(a)=2\sum_{j=1}^s\psi(ja/k),\qquad \mathcal A_p=\sum_{k=2}^N M_k\sum_{a\in\mathcal U_k}T_{k,s_k}(a)\psi(qa/k),$$ where $\mathcal U_k$ is the group of units modulo $k$, represented in $1,\ldots,k-1$.

The first term of (5) tends to one, and the harmonic term is $O(p^{-2}\log(2p))$. The sampling limit is therefore reduced to $\mathcal A_p=o(p^2)$. This is a bound on the combined signed contribution of the interior resets. The rest of the proof keeps that contribution together through its changing moduli and cutoffs.

For example, direct rational calculation at $p=3,5,7$ gives $$\mathcal S_p=\frac{11}{27},\qquad\frac{143}{225},\qquad\frac{347}{490}.$$ The asymptotic question is how the interior contribution behaves as the whole table grows.

For $L\ge1$ and a nonzero residue $a=Q\bmod k$, define $$\Delta_L(Q;k)=\mathbf 1_{a\le L\bmod k}-\mathbf 1_{k-a\le L\bmod k}, \qquad \Delta_L(0;k)=0.$$ Write $L_r=\lfloor N/r\rfloor$ and $c_{N,k}(Q)=\sum_{r\le N/k}\Delta_{L_r}(Q;k)$. Thus $\Delta_L$ is odd, has absolute value at most one, and records both ends of the actual prefix.

There are two sawtooth conventions in the argument. Dedekind sums always use $\psi$. Expanding a literal floor uses $b(x)=\{x\}-1/2$, including $b(n)=-1/2$ at integers. Direct division of $Q$ and $L$ by $k$ proves, when $Q\not\equiv0\pmod k$, $$\Delta_L(Q;k)=\frac1k-2b(Q/k) +b((Q-L-1)/k)+b((Q+L)/k).$$ The shift $-L-1$ and the term $1/k$ will both be retained.

Bounds for weighted sources

Three estimates will control different parts of the reciprocity descent. The first bounds the absolute mass of the Dedekind weights. The second uses oscillation along a reciprocal phase. The third handles a weight whose variation can be bounded while the original count source is retained. Here cyclic variation is the sum of absolute successive differences around the residue classes, and $\tau(k)$ counts the positive divisors of $k$.

The order $k\log^2(2k)$ of this absolute mass is classical [2]. The elementary proof above fixes a convenient bound for every modulus.

The first reciprocity step

Choose a threshold $H$ for the smaller member of a Dedekind pair. The pairs already below it admit a direct reciprocal-phase estimate. For the others, reciprocity separates a rational correction from a new Dedekind sum at a smaller modulus.

Inversion and reflection in (7) give $$\mathcal A_p=2\sum_{k=2}^N\sum_{\substack{0<c<k/2\\(c,k)=1}} s(c,k)c_{N,k}(q\bar c).$$ The exceptional unit at $k=2$ has zero Dedekind sum. For $H\ge1$, let $\mathcal L(H)$ be the part with $c\le H$. On $c>H$, apply (4) to write $$\mathcal A_p=\mathcal L(H)+\mathcal E(H)+\mathcal B(H),$$ where $\mathcal E$ uses $2\mathcal R(c,k)c_{N,k}(q\bar c)$ and $\mathcal B$ uses $-2s(k,c)c_{N,k}(q\bar c)$ on the same domain.

Cancellation across moduli

For a state in $\mathcal B(H)$, one has $H<c<k/2$ and $(c,k)=1$. The states with $c=1$ are already included in $\mathcal L(H)$. After removing the zero-weight tie described below, write the strict nearest-remainder step $$k=mc+\varepsilon d,\qquad 0<d<c/2, \qquad m\ge2\ (\varepsilon=1),\quad m\ge3\ (\varepsilon=-1).$$ The only coprime tie has $(c,d)=(2,1)$ and weight $s(k,2)=0$; its contribution is assigned zero. Let $\mathcal C(H,D)$ be the portion of $\mathcal B(H)$ with $d\le D$, and let $\mathcal Z(H,D)$ be its complement. This partitions the original source states without changing their weights.

Descent to the threshold

The preceding step controls pairs that reach a small remainder immediately. For the other pairs we repeat division, retaining both the correction at each step and the Dedekind sum still to be resolved.

We now take $D=H$ and retain $\mathcal Z(H,H)$. Start its original pair at $u_0=k,u_1=c$ and descend by $$u_{j-1}=m_j u_j+\varepsilon_j u_{j+1},\qquad 0<u_{j+1}<u_j/2.$$ Perform a step only when $u_{j+1}>H$, stopping before the first step crossing to $u_{j+1}\le H$. Let $J\ge1$ be the number performed and $\delta_0=1$, $\delta_j=-\varepsilon_j\delta_{j-1}$. Reciprocity gives $$\begin{aligned} s(k,c)&=f_{k,H}(c)+t_{k,H}(c),\\ f_{k,H}(c)&=-\sum_{j=1}^J\delta_j\mathcal R(u_{j+1},u_j),\\ t_{k,H}(c)&=\delta_Js(u_J,u_{J+1}). \end{aligned}$$ The corresponding split of $\mathcal Z$ is denoted $\mathcal Z(H,H)=\mathcal K(H)+\mathcal T(H)$, with the original coefficient $-2c_{N,k}(q\bar c)$ attached to both terms.

A finite nonempty word $((m_1,\varepsilon_1),\ldots,(m_s,\varepsilon_s))$ is admissible when each $\varepsilon_i\in\{-1,1\}$ and each integer $m_i$ satisfies $m_i\ge2$ if $\varepsilon_i=1$ and $m_i\ge3$ if $\varepsilon_i=-1$. Matrix products are ordered from the first digit on the left to the last on the right. These are exactly the digit restrictions of the strict nearest-remainder descent above. The matrix of a prefix carries the terminal remainder pair back to its original pair. Its determinant, equal to $+1$ or $-1$, records the orientation of that reconstruction.

The threshold $p^{11/14}$ balances the growing cost $p^{5/3}H^{1/3}$ against the decreasing cost $p^{7/2}H^{-2}$. Both have size $p^{27/14}$ at that scale. After division by $p^2$, all the accumulated corrections therefore vanish. It remains to obtain a saving for the terminal sum $\mathcal T(H)$.

The golden prefix interval

To estimate the terminal sum, we first need its full population. The matrices of the stopped paths retain both orientations. Their top rows will turn the varying path lengths into a single interval of rational coordinates.

Include the first crossing step in $P$. Its word has length at least two. The terminal domain for source index $r$ is $$\begin{gathered} u>H,\quad 1\le e\le H,\quad 2e<u,\quad(u,e)=1,\\ k=Au+Be\le L_r,\qquad c=Cu+Ee. \end{gathered}$$ The coprime tie $(u,e)=(2,1)$ has zero weight and is assigned zero contribution before imposing the strict inequality $2e<u$. All preceding remainders exceed $u$, so this is precisely a first crossing. For the sign, write the crossing step as $u_J=mu+\varepsilon e$, where $u=u_{J+1}$. Periodicity and oddness give the residual $\delta_Js(u_J,u)=\delta_J\varepsilon s(e,u)$. The original coefficient $-2$ and the update $\delta=\delta_{J+1}=-\varepsilon\delta_J$ therefore give $$-2\delta_J\varepsilon s(e,u)=2\delta s(e,u).$$ Consequently $$F_r(P)=2\delta\sum_{(u,e)\text{ in }(24)} s(e,u)\Delta_{L_r}(q\bar c;k),\qquad \mathcal T(H)=\sum_{r=1}^N\sum_P F_r(P).$$ Every state retains its original source coefficient and multiplicity.

Put $$\alpha=\frac{\sqrt5-1}{2},\qquad\beta=1-\alpha, \qquad I=(-\beta,\alpha).$$

The inverse ratio map is $z\mapsto |z|^{-1}-\lfloor |z|^{-1}+1-\alpha\rfloor$, an $\alpha$-continued-fraction map in the classical family [3]. The theorem concerns its finite prefix population. This explicit description lets us sum over every admissible path while retaining its original source weight.

Small prefix blocks

We group the terminal prefixes by the size of their denominator $A$. For small denominators, reciprocal-phase oscillation in the terminal pair gives a sufficient bound. Larger denominators will require the joined population from the golden interval.

For dyadic $K$ let $\mathcal B_r(K;H)=\sum_{K\le A<2K}F_r(P)$, including both orientations. For an active matrix, $k>A(u-e)>Au/2$, so $AH<2L_r$ and $u<2L_r/K$. Lemma 4.1 therefore gives the block’s terminal absolute mass $$W_{r,K}:=\sum_{\text{active }(u,e)}|s(e,u)| \ll(L_r/K)^2\ell^2.$$

Folding opposite orientations

The small-block bound grows with $K$. For large blocks we instead sum over the prefix population before estimating its size. The following identity transfers the orientation sign into the odd count source.

For one orientation alone the inverse of $B$ modulo $A$ selects only half the population. Equation (26) removes that restriction from the joined source. Each original contribution keeps its value, and the complete population now admits the interval summation used next.

Oscillation in the prefix denominator

Write $L=L_r$. Holding $B\ne0$ fixed, the restrictions in (28), apart from coprimality, are a single interval $$K\le A<2K,\quad A>\begin{cases}B/\alpha,&B>0,\\-B/\beta,&B<0,\end{cases} \quad A\le(L-Be)/u.$$ Globally $-2\beta K<B<2\alpha K$. Expand coprimality by $$\mathbf 1_{(A,B)=1}=\sum_{d\mid A,\ d\mid B}\mu(d),\qquad A=da.$$ Here $\mu$ is the Möbius function. On each resulting progression the literal count source becomes a sum of reciprocal phases. Its endpoint shifts must be retained even when coprimality has been removed.

The phase amplitudes range too widely for one fixed derivative order to give a saving everywhere. Orders two through fourteen cover the window below. The weakest of their savings is $\kappa=(2^{14}-2)^{-1}$, which is the derivative factor in the exponent announced in Section 1.

Power saving for large blocks

At $H=\lfloor p^{11/14}\rfloor$, split the prefix denominators at $K_0=p^{1/28}$. The small-block estimate then gives a total cost of order $p^{55/28}\ell^4$, below $p^2$. Above that cutoff, the reciprocal phases fit the derivative window of Lemma 11.2. The resulting factor satisfies $K^{-\kappa}\le p^{-\kappa/28}$ in that range, giving the exponent $\eta=\kappa/28$.

Proof of the sampling limit

Three-channel sampling corrections

The difference between the two energy readings also has a finite three-channel interpretation. Keep $N=p-1$ and $q=p^2$, and form the frequency Grams of the same sawtooths, $$H^d_{rs}=\frac4q\sum_{a=0}^{q-1}\psi(ra/q)\psi(sa/q),\qquad H^c_{rs}=4\int_0^1\psi(rx)\psi(sx)\,dx =\frac{(r,s)^2}{3rs}.$$ Their total sums are $E_p/q$ and $\mathcal J(N)$. To retain the diagonal and the two orderings of an off-diagonal pair, let $Q$ be cyclic shift on $\mathbb{R}^3$ and define, for a real symmetric matrix $H$, $$\mathfrak C(H)=\operatorname{tr}(H)I +\left(\sum_{r<s}H_{rs}\right)Q +\left(\sum_{r>s}H_{rs}\right)Q^{-1}.$$ This aggregation retains three sums from the frequency Gram. Its constant channel reads the total energy; the other two channels compare the diagonal with the off-diagonal interaction. Write $P_0=\mathbf 1\mathbf 1^{\mathsf T}/3$ for the constant-line projection in $\mathbb{R}^3$, and $P_\perp=I-P_0$ for the centered-plane projection.

The half-unit corrections are measured against the exact continuous response. The scalar sampling limit determines all three corrections in this aggregation. The capacity deficit $N-\mathcal J(N)$ remains part of the transverse response.

A unit at the common reset

Correcting a single sample is enough to make the discrete and continuous readings agree asymptotically. To see this, change the squared profile only at the origin, setting $g_N(0)=N^2$ and $g_N(x)=B_N(x)^2$ otherwise. Its integral is unchanged and its grid average increases by $N^2/p^2$. Therefore $$\mathcal S_p=\frac{N^2}{p^2} +\left(\int_0^1g_N(x)\,dx -\frac1{p^2}\sum_{a=0}^{p^2-1}g_N(a/p^2)\right).$$ The expression in parentheses tends to zero by Theorem 1.1. Equation (5) identifies it as $4\mathcal A_p/p^2-N\mathsf H_N/(3p^3)$. Thus the signed interior estimate has a direct meaning for the table. After correcting its common reset, the entire grid average approaches the continuous reading.

The correction also fixes the relation to the continuous capacity deficit. Exactly, $$p-\frac{E_p}{p^2}=[N-\mathcal J(N)]+1+\mathcal S_p =[N-\mathcal J(N)]+2+o(1).$$ One unit comes from $p-N=1$ and the other from the sampling limit. The continuous deficit $N-\mathcal J(N)$ carries its own finer asymptotics. Determining a third constant in the full energy expansion requires those terms as well; the remainder in the known capacity expansion still grows [7].

The next question is how quickly $\mathcal S_p$ approaches one. The numerical values in the secondary-term calculation [7] motivate a stronger rate.

This bound allows fluctuations on either side of one. The origin contribution $N^2/p^2$ differs from one by $O(p^{-1})$, so the proposed square-root scale concerns the combined signed interior discrepancy. It asks for stronger cancellation in the same source $\mathcal A_p$, with all its weights and cutoff terms retained.

The cubic law and its secondary term describe the growth of the carry energy. The sampling limit identifies the persistent difference between the finite table and its continuous reading. An integral ignores the value assigned at a single point. The finite table records it.

The value one comes from the prescribed joint growth of the clocks and the grid. There are $N=p-1$ clocks and $q=p^2$ samples, so the common reset contributes $N^2/q$. Its coherent square grows at the rate needed to balance the diminishing weight of a single sample. With the interior discrepancy controlled, this boundary contribution survives on its own. One sample accounts for the limiting difference of the entire table.

References