Circular sets and powers of two

[glatho...@yahoo.fr]

Hello,

Here is a particular way to construct a permutation of N elements, which is only feasible when N is a power of two: http://www.glat.info/cipo/

There seems to be a periodicity: http://www.glat.info/cipo/#o1-as-a-permutation

I'd be happy to hear comments, e.g. a simpler or shorter demo, related work, periodicity... whatever you have.

[James Waldby]

Regarding the question of whether the permutation for N = 2^q has some
periodicity, that will certainly always be the case, and it will always
be not more than 2^N - 2 (as in, for example, the cases q = 2, 3, 4, 5.)
Let CL_q denote the cycle length (ie the order or period of the
permutation). Your webpage shows values of CL_2 ... CL_10.
Values for CL_2 ... CL_26 are shown in the following table:

q: 2 2^q: 4 CL: 2
q: 3 2^q: 8 CL: 6
q: 4 2^q: 16 CL: 14
q: 5 2^q: 32 CL: 30
q: 6 2^q: 64 CL: 2280
q: 7 2^q: 128 CL: 18480
q: 8 2^q: 256 CL: 2964
q: 9 2^q: 512 CL: 10248
q: 10 2^q: 1024 CL: 6036022
q: 11 2^q: 2048 CL: 2013788
q: 12 2^q: 4096 CL: 182700
q: 13 2^q: 8192 CL: 23591700149148
q: 14 2^q: 16384 CL: 19958999294520
q: 15 2^q: 32768 CL: 6959639094969183480
q: 16 2^q: 65536 CL: 26192250762550684725571680
q: 17 2^q: 131072 CL: 3643607285677121265513086436360
q: 18 2^q: 262144 CL: 552425176567480329867600
q: 19 2^q: 524288 CL: 1104886883792843540368115115103595714814480
q: 20 2^q: 1048576 CL: 598516403943830902612507349753400
q: 21 2^q: 2097152 CL: 145205898084376835266284046071840
q: 22 2^q: 4194304 CL: 2218238870433506133002290060782067400445862406820
q: 23 2^q: 8388608 CL: 1284879737068585718960296765948422911523733198261847333520
q: 24 2^q: 16777216 CL: 44942096361329939149161891089213686455000
q: 25 2^q: 33554432 CL: 29792203744656340656203106393819329353621249230
q: 26 2^q: 67108864 CL: 100060465407260592657061740391450002788223169808280

If there's a pattern for q>5 I don't know what it is.

Here is the python 2.7 program that produced lines of the above table,
in a couple minutes of computing:

#!/usr/bin/env python
# - jiw - 19 May 2017
# Re: 23850.msg - periodicity of "a particular way to construct a
# permutation of N elements, which is only feasible when N is a power
# of two". This program creates a permutation as described at
# http://www.glat.info/cipo/ and finds the LCM of its cycle lengths to
# get the cycle length, or order, of the permutation as a whole.
from sys import argv

def gcd(a,b): # returns positive greatest common divisor of a, b
a, b = abs(a), abs(b)
while a:
a, b = b % a, a
return b

q = int(argv[1]) if len(argv)>1 else 6
t2q = 1<<q;
perm = [0]*t2q
cyco = [0]*t2q
b = 0
for i in xrange(t2q):
perm[b] = i
b = (b+i+1)%t2q

lcm = 1 # Current LCM of orders is 1
# Find next cycle and its length
for i in xrange(t2q):
if cyco[i]: continue
j = i
cylen = 0
while (1):
if cyco[j]:
break
cylen += 1
cyco[j] = 1
j = perm[j]
g = gcd(lcm, cylen)
lcm = lcm * (cylen/g)

print 'q:{:3} CL: {:9} \t2^q: {}'.format(q, lcm, t2q)

--
jiw

[James Waldby]

On Fri, 19 May 2017 08:24:32 +0000, James Waldby wrote:

> On Tue, 16 May 2017 00:53:49 -0700, glathoud_sub wrote:
>
>> Here is a particular way to construct a permutation of N elements, which is only feasible when N is a power of two: http://www.glat.info/cipo/
>>
>> There seems to be a periodicity: http://www.glat.info/cipo/#o1-as-a-permutation
>>
>> I'd be happy to hear comments, e.g. a simpler or shorter demo, related work, periodicity... whatever you have.
>
> Regarding the question of whether the permutation for N = 2^q has some
> periodicity, that will certainly always be the case, and it will always
> be not more than 2^N - 2 (as in, for example, the cases q = 2, 3, 4, 5.)
> Let CL_q denote the cycle length (ie the order or period of the
> permutation). Your webpage shows values of CL_2 ... CL_10.
> Values for CL_2 ... CL_26 are shown in the following table:

[snip]

> If there's a pattern for q>5 I don't know what it is.
>
> Here is the python 2.7 program that produced lines of the above table,
> in a couple minutes of computing:

[snip]

Following are some equivalent results, up to q=29, from a faster C
program that uses less memory. Note, to get the order of the whole
permutation, find the LCM of the separate cycle lengths. The C
program used int and long arithmetic which is too short to compute
the LCMs for q > 15.

3 cycles for q=2, 2^q=4 Lengths: 1 1 2
3 cycles for q=3, 2^q=8 Lengths: 1 1 6
3 cycles for q=4, 2^q=16 Lengths: 1 1 14
3 cycles for q=5, 2^q=32 Lengths: 1 1 30
5 cycles for q=6, 2^q=64 Lengths: 1 1 40 3 19
7 cycles for q=7, 2^q=128 Lengths: 1 1 48 3 55 14 6
5 cycles for q=8, 2^q=256 Lengths: 1 1 247 3 4
7 cycles for q=9, 2^q=512 Lengths: 1 1 488 3 6 6 7
5 cycles for q=10, 2^q=1024 Lengths: 1 1 818 47 157
5 cycles for q=11, 2^q=2048 Lengths: 1 1 1652 23 371
5 cycles for q=12, 2^q=4096 Lengths: 1 1 4060 25 9
9 cycles for q=13, 2^q=8192 Lengths: 1 1 3609 3754 412 321 79 12 3
11 cycles for q=14, 2^q=16384 Lengths: 1 1 15748 190 24 292 71 22 13 13 9
11 cycles for q=15, 2^q=32768 Lengths: 1 1 20161 11349 305 281 72 44 333 218 3
11 cycles for q=16, 2^q=65536 Lengths: 1 1 16759 20128 8072 17231 2377 579 295 60 33
15 cycles for q=17, 2^q=131072 Lengths: 1 1 85861 26603 9389 3365 3887 594 488 118 682 49 23 6 5
13 cycles for q=18, 2^q=262144 Lengths: 1 1 159827 89991 5465 5749 592 100 231 42 118 24 3
19 cycles for q=19, 2^q=524288 Lengths: 1 1 176243 35639 211265 28496 59029 4245 1239 6122 632 713 36 244 59 146 133 39 6
15 cycles for q=20, 2^q=1048576 Lengths: 1 1 620076 216520 131454 68118 1235 7535 1028 225 2111 213 36 20 3
17 cycles for q=21, 2^q=2097152 Lengths: 1 1 583840 993084 31835 87941 394263 3389 1648 459 273 8 306 10 35 45 14
21 cycles for q=22, 2^q=4194304 Lengths: 1 1 1487646 942359 429054 1119526 28806 64446 118037 3238 291 323 126 186 118 102 4 10 12 11 7
21 cycles for q=23, 2^q=8388608 Lengths: 1 1 2040680 2462220 2542051 1138236 93072 14243 45880 19664 16473 2160 6319 2917 514 1414 2598 19 23 118 5
19 cycles for q=24, 2^q=16777216 Lengths: 1 1 12137774 4004239 271250 253890 43860 4132 33597 25495 2575 67 35 157 116 4 6 8 9
17 cycles for q=25, 2^q=33554432 Lengths: 1 1 28169497 1019221 1401622 2552414 356682 10242 14735 8223 21006 135 566 45 15 21 6
17 cycles for q=26, 2^q=67108864 Lengths: 1 1 29360424 32223531 3530597 67418 809707 932310 83093 99109 248 248 1612 364 166 14 21
25 cycles for q=27, 2^q=134217728 Lengths: 1 1 87591110 34361487 3291274 3343185 3360928 353498 323522 1345478 158252 47767 17776 11159 84 5927 59 2343 2681 530 235 162 208 30 31
23 cycles for q=28, 2^q=268435456 Lengths: 1 1 232647749 5559122 24918738 197080 384941 3742461 525140 62977 48736 21684 278834 2721 1625 8993 16632 13525 3073 153 1262 3 5
23 cycles for q=29, 2^q=536870912 Lengths: 1 1 379598603 129063661 26279056 137686 665648 222289 483286 10615 41767 80276 94323 5066 106713 15498 59199 2699 2816 1579 113 10 7

real 0m53.153s

--
jiw

[glatho...@yahoo.fr]

Thanks very much for the answers, James.
I have added your numerical results to the relevant article section:
http://www.glat.info/cipo/#o1-as-a-permutation

Am Sonntag, 21. Mai 2017 10:49:45 UTC+2 schrieb James Waldby:
> On Fri, 19 May 2017 08:24:32 +0000, James Waldby wrote:
>

> [...]

>
> > Regarding the question of whether the permutation for N = 2^q has some
> > periodicity, that will certainly always be the case, and it will always
> > be not more than 2^N - 2 (as in, for example, the cases q = 2, 3, 4, 5.)

Even if that might seem too simple of a question, how do you prove the 2^N - 2 limit?

> [...]

I understand these would be the (cylen/g) values as expressed in the Python program - please correct me if I am wrong.

In the results you provided the number of cycles remains <= q.

Best regards,
Guillaume

[James Waldby]

On Mon, 22 May 2017 11:06:48 -0700, glathoud_sub wrote:
> Thanks very much for the answers, James.
> I have added your numerical results to the relevant article section:
> http://www.glat.info/cipo/#o1-as-a-permutation
> Am Sonntag, 21. Mai 2017 10:49:45 UTC+2 schrieb James Waldby:
>> On Fri, 19 May 2017 08:24:32 +0000, James Waldby wrote:
>> [...]
>>
>> > Regarding the question of whether the permutation for N = 2^q has some
>> > periodicity, that will certainly always be the case, and it will always
>> > be not more than 2^N - 2 (as in, for example, the cases q = 2, 3, 4, 5.)
>
> Even if that might seem too simple of a question, how do you prove the 2^N - 2 limit?

At the moment I wrote N=2^q and said 2^N-2 [ie 2^((2^q)-2)] is an upper
bound, I was thinking of consequences of the AM–GM inequality (see eg
<https://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means>)
by which one can show that for a number K, 2^K > max(Product(P(K))), where
P(K) represents any additive partition of K. However, shortly after
writing it, I got off track and wrote "as in, for example, the cases
q = 2, 3, 4, 5" which actually is not relevant to that overall upper bound.

What the cases q = 2, 3, 4, 5 illustrate is that any individual cycle of
the permutation has length not more than 2^q - 2, because there are at
least two 1-cycles, one for each of the first two elements, which leaves
at most 2^q - 2 elements for any subsequent cycles. (The lengths of the
cycles of the permutation add up to the permutation's length. The order
of the permutation -- that is, its periodicity -- is the least common
multiple of the lengths of its disjoint cycles, as explained in
<https://en.wikipedia.org/wiki/Permutation#Cycle_notation>.)

For a tighter upper bound than 2^((2^q)-2), suppose there were a large
number of p-cycles, with p taking on a series of distinct prime values.
(This will maximize the LCM of cycle lengths.) If the largest prime
is h, the order is the product of primes up to h, that is, h#
using notation shown in <https://en.wikipedia.org/wiki/Primorial>.

We suppose h to be the largest prime such that the sum of 2, 3, 5, ...
h doesn't exceed 2^q - 2. <https://oeis.org/A034387> shows an
asymptotic value of n^2 / (2 log n) for the sum of primes =< n. If
h^2 / (2 log h) ~ 2^q - 2, we have q log 2 ~ 2 log h and
h ~ exp((q log 2)/2) = 2^(q/2). As log(h#) ~ h, this gives a
crude upper bound on permutation order of h# ~ exp(2^(q/2)).

...
>> Following are some equivalent results, up to q=29, from a faster C
>> program that uses less memory. Note, to get the order of the whole
>> permutation, find the LCM of the separate cycle lengths. The C
>> program used int and long arithmetic which is too short to compute
>> the LCMs for q > 15.
>>
>> 3 cycles for q=2, 2^q=4 Lengths: 1 1 2

...

>> 19 cycles for q=24, 2^q=16777216 Lengths: 1 1 12137774 4004239 271250 253890 43860 4132 33597 25495 2575 67 35 157 116 4 6 8 9
>> 17 cycles for q=25, 2^q=33554432 Lengths: 1 1 28169497 1019221 1401622 2552414 356682 10242 14735 8223 21006 135 566 45 15 21 6
>> 17 cycles for q=26, 2^q=67108864 Lengths: 1 1 29360424 32223531 3530597 67418 809707 932310 83093 99109 248 248 1612 364 166 14 21
>> 25 cycles for q=27, 2^q=134217728 Lengths: 1 1 87591110 34361487 3291274 3343185 3360928 353498 323522 1345478 158252 47767 17776 11159 84 5927 59 2343 2681 530 235 162 208 30 31
>> 23 cycles for q=28, 2^q=268435456 Lengths: 1 1 232647749 5559122 24918738 197080 384941 3742461 525140 62977 48736 21684 278834 2721 1625 8993 16632 13525 3073 153 1262 3 5
>> 23 cycles for q=29, 2^q=536870912 Lengths: 1 1 379598603 129063661 26279056 137686 665648 222289 483286 10615 41767 80276 94323 5066 106713 15498 59199 2699 2816 1579 113 10 7

> I understand these would be the (cylen/g) values as expressed in the Python program - please correct me if I am wrong.

Rather than cycle lengths divided by a GCD, the 'Lengths:' numbers in the
previous post are raw cycle lengths. My C program doesn't use big-number
arithmetic -- it uses native 32- and 64-bit native arithmetic -- so it
doesn't compute the LCM. At q=16, the LCM starts exceeding 64 bits.

> In the results you provided the number of cycles remains <= q.

That's true; I was surprised how low the number of disjoint cycles is,
and don't know how to explain it.

--
jiw

[glat...@yahoo.fr]

Hello,


some further progress: I have optimized your original algorithm (Python code) into a 1-pass, 1-bit per element algorithm:

https://github.com/glathoud/cipo/blob/master/cycles/cipo_cycles.d

This led to results up to q=38:

https://raw.githubusercontent.com/glathoud/cipo/master/cycles/cipo_cycles.result.txt

Remark: n_cycle remains relatively low, indeed < q in all cases obtained so far (up to q=38).

.

For what it's worth, I also computed the period (LCM) up to q=35, in the form of prime factors (to overcome the 64-bit limitation):

https://raw.githubusercontent.com/glathoud/cipo/master/period/cipo_period_of_cycles.result.txt

I am not exactly sure how to comment those big prime numbers, though.

.

Back to the number of cycles: I compared with the number of cycles of random permutations, so far up to q=29, and could *always* find at least one random permutation with n_cycle >= q:

https://raw.githubusercontent.com/glathoud/cipo/master/period/cipo_period_of_random_permutation.result.txt

This can be contrasted with the results obtained so far:

> https://raw.githubusercontent.com/glathoud/cipo/master/cycles/cipo_cycles.result.txt
>
> Remark: n_cycle remains relatively low, indeed < q in all cases up to q=38.

.

Maybe that would make a conjecture "n_cycle < q for *all* q" interesting enough. Not sure how to attack the proof, though.

.

Best regards,
Guillaume

[Simon Roberts]

this may help, I hope,

On Friday, June 23, 2017 at 3:14:28 PM UTC-4, Simon Roberts wrote:
> givens (almost arbitrary): x^(2^(p)) and odd prime , p,
>
> does not divide x and x=/= 1 (mod p).
>
> derivation with result at bottom.
>
> x^(2^(p)) = x^((2 + p*R_0)) = x^2(x^R_0) (mod p)
>
> that is,
>
> x^(2^(p-1)) = (x^R_0) = 1 (mod p)
>
>
> (p is odd prime).
>
> now 2^p = (1 + 1)^p = 2 + p*R_0
>
> = 2 + p*SUM_{I = 1 to (p-1)) of (p -1)! / [I!(p-I)!]
>
> therefore,
>
> R_0 = SUM_{I = 1 to (p-1)) of (p -1)! / [I!(p-I)!]
>
> (BTW R_0 = 2 + SUM_{I = 2 to (p-2)) of (p -1)! / [I!(p-I)!])
>
>  
>
>  and
>
> x^(R_0) = 1 (mod p)

R_0 == (2^p - 2)/p. wow.

further,

x^[(2^p - 2)/p] = 1 (mod p)

or

x^(2^p - 2) = 1 (mod p)

or

x^(2^p) = x^2 (mod p)

or

x^(2 + p*R_0) = x^2 (mod p)

x^(p*R_0) = 1 (mod p)

roger that.

Simon

[glat...@yahoo.fr]

Thanks. Can you describe in one or two sentences the meaning of what you did?

Best regards,
Guillaume