[math-fun] Mapping problem
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?
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] --
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
Hi, Victor. I was thinking about David Wilson's mapping problem and decided that it would be interesting to reformulate it somewhat less randomly as follows: Given the ring Z_n (Z/nZ) and any polynomial P(x) in Z[x], find the cycles from iterating P on Z_n. OK, that would be interesting. But what is the (or a) set of polynomials that determine *distinct* self-mappings of Z_n ??? After all there are only n^n self-mappings in all. Clearly polynomials P(x) and Q(x) are equal on Z_n when their difference vanishes everywhere. Aha, so look at that ideal — call it I_n — of all P(x) vanishing on every element of Z_n. Question: What is I_n ??? P(x) is a P.I.D. so I_n must be generated by one polynomial, so a unique monic one. What is it ??? Then of course the distinct polynomials correspond to the quotient Z[x] / I_n. What does that look like? *Then* we could start finding the cycle structure corresponding to each element of this quotient. ----- And I suppose one could ask the same question of any finite field F(p^n). Or would that be trivial? —Dan
that ideal — call it I_n — of all P(x) vanishing on every element of Z_n.
Question: What is I_n ??? P(x) is a P.I.D. so I_n must be generated by one polynomial, so a unique monic one. What is it ???
Then of course the distinct polynomials correspond to the quotient Z[x] / I_n. What does that look like?
*Then* we could start finding the cycle structure corresponding to each element of this quotient.
Well, no. If n is composite then we can not necessarily divide through by the leading coefficient. —Anonymous
Slight correction: f(2^m) = 2 (corresponding to the set {0,1}). So, in fact f(n) = 1 + odd part of phi(n) Victor On Wed, Nov 16, 2016 at 1:28 PM, Victor Miller <victorsmiller@gmail.com> wrote:
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
participants (4)
-
Dan Asimov -
David Wilson -
Tomas Rokicki -
Victor Miller