Concernning f(p^m): the set S must be a subset of Z(p^m)* union 0. Suppose not. Then there are elements in S of the form p^j*a, for some invertible a, and j>0. Let k be the smallest such j that occurs. In order of p^k*a to be in S, there must be an element of the form p^(k/2)*a' for some invertible a', which is a contradiction. Now, by the theorem of the primitive element Z(p^m)* is a cyclic group (provided that p is odd, it's a product of a cyclic group and a group of order 2 for the case that p is 2). So the problem reduces to the problem of -- given a finite abelian group G, find the largest subset S which is fixed by multiplying by 2 (which is what squaring becomes). We can write G as a director product H * J, where H has 2 power order, and J has odd order. By the same sort of argument at the beginning our set S must be the direct product of a subset of H by a subset of J. However it's easy to see that multiplying by 2 is a permutation on J, and that the only nonempty subset of H left invariant by multiplying by 2 is the identity. Thus we have f(p^m) = 1 + the odd part of phi(p^m). = 1 if p = 2, and 1 + p^(m-1)*(odd part of p-1) if p is odd. Victor On Tue, Nov 15, 2016 at 12:32 AM, Tomas Rokicki <rokicki@gmail.com> wrote:
If n=p_1*p_2*...*p_m where p_1..p_m are prime powers, then f(n) = f(p_1)*f(p_2)*...*f(p_m). (Chinese remainder theorem.)
If p is prime and m>0, then f(p^{m+1})=p*f(p^m)-p+1. (Empirical observation; no proof yet.)
I have not yet figured out f(p) for p prime.
On Tue, Nov 8, 2016 at 7:46 PM, David Wilson <davidwwilson@comcast.net> wrote:
Let S(n) be the largest subset of Z(n) fixed by the mapping n -> n^2, and let f(n) = |Z(n)|. For example, S(25) = {0, 1, 6, 11, 16, 21} is the largest set of residues modulo 25 fixed by the mapping n -> n^2, so f(25) = |S(25)| = 6. Can you find a formula for f(n) in terms of n?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun