More digital silliness

[Max Alekseyev]

Corrections:

1) The number of square roots of any number b modulo m (where b and m
are coprime) is
2^omega(m), where omega(m) is the number of distinct prime divisors of
m, only if m is odd or the power of 2 in its prime factorization is 2
(i.e., valuation(m,2)=0 or valuation(m,2)=2 correspondingly).
It is twice as much for valuation(m,2)>2 and twice as low for valuation(m,2)=1.

2) Solutions to the system of congruences:

y = x * r1 (mod m)
z = x * r2 (mod m)

may not be necessary coprime to m. Therefore, we need to go over all
square divisors d^2 | m, solve the reduced system:

y' = x' * r1 (mod m/d^2)
z' = x' * r2 (mod m/d^2)

and let x = x' * d, y = y' * d, z = z' * d to get a solution to the
original system.

This also has certain implication to the chance of the solution
existence: it is larger for m with a large square divisor d^2,
especially if m/d^2 and d are not coprime (ideally if d is square-free
and m is divisible by d^3, so that gcd(m/d^2,d)=d).

Regards,
Max

On Jan 11, 2008 7:40 PM, Max Alekseyev <maxale at gmail.com> wrote:
>
> On Jan 9, 2008 11:33 AM, David W. Wilson <wilson.d at anseri.com> wrote:
>
> > Let an n-digit number be valid if it does not start or end with 0.
> > Let a rotation of n be gotten by rotating its digits. Thus the rotations of
> > 256 are 256, 562 and 625.
> > We note that 256 has two valid square rotations, 256 and 625.
> > Is there a number with more than two valid square rotations?
>
> Surprisingly, such numbers are related to the existence of "small"
> solutions to some system of linear modular equations.
> Below I will describe this connection and suggest a fast method for
> finding such numbers.
>
> Let d be the base of our numeral system (e.g., d=10). Suppose that the
> number N consists of n digits, and the rotations are done by u, v, and
> w digits so that n=u+v+w. Then there exist positive integers
> a,b,c,x,y,z such that
>
> a*d^(v+w) + b*d^w + c = x^2
> b*d^(w+u) + c*d^u + a = y^2
> c*d^(u+v) + a*d^v + b = z^2
>
> where the numbers a*d^(v+w) + b*d^w + c, b*d^(w+u) + c*d^u + a,
> c*d^(u+v) + a*d^v + b represents the three rotations of our number N
> in the base d. The numbers a,b,c have in the base d the length u,v,w
> correspondingly, i.e.:
>
> d^(u-1) < a < d^u
> d^(v-1) < b < d^v
> d^(w-1) < c < d^w
>
> implying that
>
> d^(u+v+w-1) < x^2, y^2, z^2 < d^(u+v+w)
> and
> sqrt(d/m) < x, y, z < sqrt(m)
>
> where m = d^(u+v+w) - 1.
> This number m turns to be very important for finding a,b,c (or x,y,z)
> since the system of equations above is equivalent to (multiplying the
> first equation by d^u and subtracting the second etc.):
>
> x^2 * d^u - y^2 = a * m
> y^2 * d^v - z^2 = b * m
> z^2 * d^w - x^2 = c * m
>
> that is equivalent to the following system congruences:
>
> y^2 = x^2 * d^u (mod m)
> z^2 = x^2 * d^(u+v) (mod m)
>
> We are interested in "small" solutions to this system, namely, that
> satisfy sqrt(d/m) < x, y, z < sqrt(m). Any such solution will give us
> the requiqed a,b,c whose concatenation in the base d is x^2, while the
> concatenation of b,c,a is y^2 and the concatenation of c,a,b is z^2.
>
> Let R1 and R2 be respectively the sets of all square roots of d^u and
> d^(u+v) modulo m. Note that each of them is either empty (when the
> corresponding power of d is not a square modulo m) or has multiplicity
> 2^omega(m), where omega(m) is the number of distinct prime divisors of
> m.
> If either of R1, R2 is empty, our system of congruences does not have
> a solution, meaning that the required number does not exist for chosen
> parameters d,u,v,w. Otherwise for every r1 from R1 and every r2 from
> R2 we have a system of congruences:
>
> y = x * r1 (mod m)
> z = x * r2 (mod m)
>
> where we still interested for "small" solutions. We can reformulate
> this problem as Closest Vector Problem (CVP) to attack it with LLL
> algorithm.
>
> Namely, let C be the integer median of the interval
> [sqrt(d/m),sqrt(m)] and let D be an integer half of its length, so
> that the distance from every integer in this interval to C is at most
> D. Then a "small" solutions (x,y,z) belongs to the lattice L(M)
> generated by the columns of the following matrix
>
> [ 1 m 0 0 ]
> [ r1 0 m 0 ] = M
> [ r2 0 0 m ]
>
> and is close to the vector (C,C,C). Therefore, we need to find the
> closest vector (x,y,z) to (C,C,C) in the lattice L(M), and if this
> vector is close enough to (C,C,C), it will represent a required
> "small" solution.
>
> I've implementated this approach in PARI/GP (can share if anybody
> wants to play with different bases) and for d=10 tested all numbers up
> to the length n=u+v+w=30. No solutions have been find.
>
> This approach also leads to the following theoretical estimate of the
> chance that required number of the length n exists. Namely, it's
> roughly:
> 4^omega(d^n - 1) / d^(n/2)
> So, I think that for all bases d>=4 there exists only a finite number
> of such numbers (unless there is some clear pattern).
>
> Regards,
> Max
>