退出

What extra state data is needed to make this affine-family transition deterministic?

数论 Math StackExchange 0 票 0 回答 24 浏览 提问者: JaanA 2026-06-11 10:38
number-theory elementary-number-theory modular-arithmetic

问题内容

Consider affine families

$$ Q(u)=2^t3^{16}u+B, $$

with $t\ge 3$ and $2^t\mid 3B-1$. Set

$$ C_0=\frac{3B-1}{2^t}. $$

Then

$$ 3Q(u)-1 =2^t3^{17}u+(3B-1) =2^t(3^{17}u+C_0). $$

Suppose we restrict to a subfamily where, after the fixed factor $2^t$, another $2^\lambda$ divides the remaining factor:

$$ 2^\lambda\mid 3^{17}u+C_0. $$

Since $3^{17}$ is odd, this selects one residue class

$$ u\equiv r\pmod {2^\lambda}, \qquad r\equiv -(3^{17})^{-1}C_0\pmod {2^\lambda}. $$

Writing $u=2^\lambda v+r$, the family becomes

$$ Q(u)=2^{t+\lambda}3^{16}v+B', \qquad B'=2^t3^{16}r+B. $$

The new normalized constant is

$$ C_0' =\frac{3B'-1}{2^{t+\lambda}} =\frac{3^{17}r+C_0}{2^\lambda}. $$

This is an integer because $r$ was chosen so that

$$ 2^\lambda\mid 3^{17}r+C_0. $$

Modulo $3^{17}$,

$$ 2^\lambda C_0'\equiv C_0\pmod {3^{17}}, $$

so

$$ C_0'\equiv 2^{-\lambda}C_0\pmod {3^{17}}. $$

For example, if $t=3$, $B=3$, and $\lambda=3$, then $C_0=1$. Since

$$ 3^{17}\equiv3\pmod8 $$

and $3^{-1}\equiv3\pmod8$, the survivor residue is

$$ r\equiv -3C_0\equiv -3\equiv5\pmod8. $$

Then

$$ C_0'=\frac{3^{17}\cdot5+1}{8}=80,712,602. $$

Equivalently,

$$ \frac{3Q(8v+5)-1}{64} =3^{17}v+80,712,602, $$

so the parameter $v$ only changes the result by a multiple of $3^{17}$.

One subtlety is that the condition

$$ 2^\lambda\mid 3^{17}u+C_0 $$

only means that there are at least $\lambda$ extra factors of $2$. If $\lambda$ is meant to be the exact exponent removed at this step, one would also need

$$ 2^{\lambda+1}\nmid 3^{17}u+C_0. $$

For the purpose of the state question, I am thinking of $\lambda$ as part of a finite row choice: a row either records the exact exponent, or records a branch that may later be refined.

The part I am unsure about is the state information.

The congruence modulo $3^{17}$ gives the next odd-modulus coordinate once $\lambda$ and the chosen residue class are known. But the choice of that residue class uses $C_0 \bmod 2^\lambda$, not just $C_0 \bmod 3^{17}$.

For example, take $C_0=1$ and $C_0=1+3^{17}$. These are the same modulo $3^{17}$, but not modulo $8$, since

$$ 3^{17}\equiv3\pmod8. $$

So

$$ 1+3^{17}\equiv4\pmod8. $$

For $\lambda=3$, using $(3^{17})^{-1}\equiv3\pmod8$, the first value gives

$$ r\equiv -3\cdot1\equiv5\pmod8, $$

while the second gives

$$ r\equiv -3\cdot4\equiv4\pmod8. $$

Thus two constants that are equal modulo $3^{17}$ can lead to different residue classes modulo $8$.

So my question is about the proposed state variable. Is it correct that $C_0 \bmod 3^{17}$ alone cannot determine the next branch? It seems that one also has to record, in some finite way, the relevant $2$-adic data needed to determine $\lambda$ and $r \bmod 2^\lambda$.

If the possible values of $\lambda$ are not bounded or otherwise restricted to a finite list, then I do not see how this would give a finite-state transition.

回答 (0)

暂无回答记录。