What extra state data is needed to make this affine-family transition deterministic?
问题内容
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)
暂无回答记录。