[seqfan] Re: Mapping problem

[Joerg Arndt]

* David Wilson <davidwwilson at comcast.net> [Nov 09. 2016 10:32]:
> 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?
>

I speculate that all fourth powers give the set.
Here I only look at the multiplicative group (units mod n).

The following is a quick shot:
(PARI) a(n)=my(p=eulerphi(n)); sumdiv(p,d,if((p/d)%4!=0,0,eulerphi(d)))

vector(25,n,a(n))
gives
[0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 3, 0, 2, 2, 4, 0, 0, 2, 3, 0, 0, 2, 5]
The final 5 for all elements you gave, except 0.

The singly generated multiplicative groups (those having a primitive root)
are isomorphic to additive groups of the same cardinality.
Squaring in the mult. group maps to doubling in the additive group.
>From the(se) elements (of the form 2*? mod cardinality) we only
take those that are mapped to from said set via doubling.
So we are left with all elements 4*? mod cardinality.

That should give the same result.

Example: (mult. group mod 13 isom. to add. group mod 12)
There are 3 elements that are a multiple of 4:
m=12; vector(m,j, (4*j)%m )
[4, 8, 0, 4, 8, 0, 4, 8, 0, 4, 8, 0]
This checks the value for 13 above.

But for 11 (add. gr. 10) I get 5 elements:
? m=10; vector(m,j, (4*j)%m )
[4, 8, 2, 6, 0, 4, 8, 2, 6, 0]
That does not match the 0 above...

So shurely shome mishtake shomwhere.

Best regards,   jj


> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/