mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-05-10, 23:07   #1
Dougy
 
Dougy's Avatar
 
Aug 2004
Melbourne, Australia

23×19 Posts
Default An arithmetic permutation

This problem was proposed by Ian Wanless. It's published in a list of problems from the 21st British Combinatorial Conference: P.J. Cameron, Research Problems from the BCC21, Discrete Mathematics (2009), doi:10.1016/j.disc.2009.04.016

Let p be a prime congruent to 1 or 3 modulo 8. Let S and N be the sets of quadratic residues and non-residues modulo p. Consider the permutation \pi whose two-row form is the following array L (all entries modulo p):

L_{1,i}=\begin{cases}0 & \text{if } i=0 \\ -i & \text{if } i \in S \\ 2i & \text{if } i \in N\end{cases}

L_{2,i}=L_{1,i-1}+1

For example, when p=11

L=\left(\begin{array}<br />
0 & 10 & 4 & 8 & 7 & 6 & 1 & 3 & 5 & 2 & 9 \\<br />
10 & 1 & 0 & 5 & 9 & 8 & 7 & 2 & 4 & 6 & 3<br />
\end{array}\right)

and \pi is the single cycle (0,10,1,7,9,3,2,6,8,5,4).

Conjecture: Always \pi is a single cycle of order p.

Comment: The conjecture can be formulated in terms of permutation polynomials. It has been verified for p < 10^7.
Dougy is offline   Reply With Quote
Old 2009-05-11, 11:55   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by Dougy View Post
This problem was proposed by Ian Wanless. It's published in a list of problems from the 21st British Combinatorial Conference: P.J. Cameron, Research Problems from the BCC21, Discrete Mathematics (2009), doi:10.1016/j.disc.2009.04.016

Let p be a prime congruent to 1 or 3 modulo 8. Let S and N be the sets of quadratic residues and non-residues modulo p. Consider the permutation \pi whose two-row form is the following array L (all entries modulo p):

L_{1,i}=\begin{cases}0 & \text{if } i=0 \\ -i & \text{if } i \in S \\ 2i & \text{if } i \in N\end{cases}

L_{2,i}=L_{1,i-1}+1

For example, when p=11

L=\left(\begin{array}<br />
0 & 10 & 4 & 8 & 7 & 6 & 1 & 3 & 5 & 2 & 9 \\<br />
10 & 1 & 0 & 5 & 9 & 8 & 7 & 2 & 4 & 6 & 3<br />
\end{array}\right)

and \pi is the single cycle (0,10,1,7,9,3,2,6,8,5,4).

Conjecture: Always \pi is a single cycle of order p.

Comment: The conjecture can be formulated in terms of permutation polynomials. It has been verified for p < 10^7.
I am obviously having a stupidity attack, but it is not clear to me
how \pi is derived from L. Please explain further.
There may be a purely group-theoretic explanation.

Also, what does the word 'single' mean as in 'single cycle'?
Clearly \pi is a 'single' cycle. I fail to see how anyone would
consider it to be more than one cycle.

May I also suggest that you be careful in using the word 'cycle' in a
context that is both number-theoretic and combinatoric. In a number
theory sense, a 'cycle' is the full orbit of (the powers of an integer) mod p.
It can not contain 0 unless the integer is not co-prime to p.
You mean 'cycle' in its combinatoric sense, as a permutation.
R.D. Silverman is offline   Reply With Quote
Old 2009-05-11, 12:14   #3
Chris Card
 
Chris Card's Avatar
 
Aug 2004

100000012 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I am obviously having a stupidity attack, but it is not clear to me
how \pi is derived from L. Please explain further.
There may be a purely group-theoretic explanation.
L defines the permutation of the numbers 0 - 10, so 0 -> 10, 10 -> 1 etc.
\pi is simply writing the permutation as a product of cycles, and in this case there is only one cycle in the product.
Quote:
Also, what does the word 'single' mean as in 'single cycle'?
Clearly \pi is a 'single' cycle. I fail to see how anyone would
consider it to be more than one cycle.

May I also suggest that you be careful in using the word 'cycle' in a
context that is both number-theoretic and combinatoric. In a number
theory sense, a 'cycle' is the full orbit of (the powers of an integer) mod p.
It can not contain 0 unless the integer is not co-prime to p.
You mean 'cycle' in its combinatoric sense, as a permutation.
Isn't 'cycle' in the sense you give for number theory simply a special case of the group-theoretical meaning for cycle? ... since there is only one cycle in the permutation generated by powers (1, p, p^2, ...) for integers mod p.

Chris
Chris Card is offline   Reply With Quote
Old 2009-05-11, 12:25   #4
maxal
 
maxal's Avatar
 
Feb 2005

22·32·7 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I am obviously having a stupidity attack, but it is not clear to me
how \pi is derived from L. Please explain further.
\pi is defined as a permutation that maps an element L_{1,i} to an element L_{1,i-1}+1 for every i=0,1,\dots,p-1 (I agree, it's somewhat obscure notation).

Quote:
Also, what does the word 'single' mean as in 'single cycle'?
"Cycle" here means a cycle in a permutation. As we know, every permutation is the product of disjoint cycles. The goal here is to prove that \pi represents a single cycle and of order p, meaning that this cycle contains all residues from 0 to p-1.

Last fiddled with by maxal on 2009-05-11 at 12:26
maxal is offline   Reply With Quote
Old 2009-05-12, 21:37   #5
Dougy
 
Dougy's Avatar
 
Aug 2004
Melbourne, Australia

23×19 Posts
Default

Yep, I think maxal and Chris Card have got the correct idea. I spoke to Ian and he wasn't even aware that this had been published. He mentioned this conjecture to me several years ago and I wasn't able to make any progress.

I thought I'd just post a copy of it here, in case anyone was interested.
Dougy is offline   Reply With Quote
Old 2010-05-30, 02:20   #6
ccorn
 
ccorn's Avatar
 
Apr 2010

22·37 Posts
Default

Note that \pi takes the form of a commutator: Define

A, B: \mathbb{Z}/p\mathbb{Z}\mapsto\mathbb{Z}/p\mathbb{Z}
A(X) = X+1
B(i)=L_{1,i}
A represents the cycle (0,1,...p-1), and B is a permutation as long as \left(\frac{-2}{p}\right)=+1 (which is why p must be 1 or 3 mod 8). Then \pi = A\,B\,A^{-1}\,B^{-1}.

Hence \pi is in the commutator subgroup of S_p which is A_p. This implies that \pi is an even permutation.
This is compatible with the conjecture because p is odd, and odd-length cycles are even permutations.

\pi being an even permutation also means that \pi cannot have a cycle decomposition into an even number of cycles (with fixed points counted as well), because then the number of even-length cycles would have to be odd, which would make \pi an odd permutation. Hence, if \pi is not a p-cycle, its shortest cycle has length at most floor(p/3). If additionally \pi has no fixed points (which can be shown), then its longest cycle has length at most p-4.
ccorn is offline   Reply With Quote
Old 2010-06-01, 17:23   #7
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

11001010010102 Posts
Default

Quote:
Originally Posted by Dougy View Post
This problem was proposed by Ian Wanless.
I used to teach him at St Paul's Skool. Smart guy!
davieddy is offline   Reply With Quote
Old 2010-06-13, 00:39   #8
ccorn
 
ccorn's Avatar
 
Apr 2010

22×37 Posts
Default Program

I have written a small ISO C++ program for numerical verification of the conjecture.

The program reads a number p from stdin, checks it for validity (e.g. primality and congruence to 1 or 3 mod 8) and checks by brute force whether \pi^p(0) = 0 where \pi is the permutation map associated with p. The result is reported to stdout, then the next input number is read, and so on, until the input reaches end-of-file (which is Control-D for tty users).

Correctness: Consider the cycle decomposition of \pi. The program checks whether the cycle containing 0 has length dividing p. Since p is prime and \pi(0) \neq 0, the checked condition is equivalent to \pi being a p-cycle.

Unfortunately, I have not found a representation of \pi that remains compact when nested. Therefore, I have not implemented a square-and-multiply scheme. Instead, the program walks through the iterations one by one. Thus it uses O(p) steps and O(p log p) bit operations.

On 32-bit systems with 256 MBytes available for program data, the program can check primes up to 2^31. On platforms with size_t longer than 32 bits, you can reasonably try p values up to the amount of available RAM, measured in bits.

The reason why the program needs O(p) memory is that every iteration needs to evaluate two Jacobi symbols. Instead of calculating them from scratch each time, the program first sets up a table with all Jacobi symbol values and then looks them up during the iteration. The setup goes fast: To enumerate the first n squares, you just need to add the first n odd positive integers. (This is done mod p of course.)

While the setup is easy but not very cache-friendly, the lookups made during the iteration happen to reference nearby locations in at least 75% of the time, thus the processor's caches are used efficiently.

As a side benefit, the setup can check whether the input number is prime or not, simply by testing if a square has been tabled more than once. (Prime powers are ruled out too because the program marks 0 as a "square" before filling the rest of the table.)

Here are some examples, run on my Powerbook G4 (a PPC 7450 @ 1.5 GHz). Lines that begin with $ contain shell (bash) commands. I use Pari/GP to output suitable primes for the program.
Code:
$ g++-4.3 -O3 arithperm.cc -o arithperm
$ max=100; echo "default(primelimit,$max); \
forprime(p=3,$max,if(((p%8)-(p%4))==0,print(p)))" | gp -q | \
./arithperm "$max"
3: true
11: true
17: true
19: true
41: true
43: true
59: true
67: true
73: true
83: true
89: true
97: true
Some benchmarks:
Code:
$ time echo 100000049 | ./arithperm
100000049: true

real    0m11.585s
user    0m11.300s
sys     0m0.115s
Thus each iteration takes less than 120ns (180 cycles) on average.
Let's test the largest prime below 2^31 that is congruent to 1 or 3 mod 8:
Code:
$ time echo 2147483587 | ./arithperm
2147483587: true

real    5m46.655s
user    5m38.374s
sys     0m2.909s
At this extreme, each iteration takes almost 160ns (240 cycles) on average.

I have tried another version of the program that does not use a table and computes Jacobi symbols directly. After all, computing a Jacobi symbol value of two n-bit machine-word integers should need only two additional registers and at most about 2n shifts, subtracts, negations, tests and jumps. With n=32 and zero-cycle branch cost, this should deliver comparable performance to the table-based approach.

However, my high-level C++ Jacobi code is about five times slower yet, therefore I present the table-based version here for experiments.

For details, look at the source . If you want to check the iteration, uncomment the line containing cerr << in the function permute, recompile, run and input 11 (or whatever you can check). Do not forget to comment out that line and to recompile again before starting larger runs.
Attached Files
File Type: zip arithperm.zip (3.8 KB, 64 views)
ccorn is offline   Reply With Quote
Old 2010-06-17, 22:01   #9
ccorn
 
ccorn's Avatar
 
Apr 2010

100101002 Posts
Default More timings

My machine has a 500 kByte (= 4 MBit) L2 cache; therefore I ran the following test:
Code:
$ time echo 4000043 | ./arithperm
4000043: true

real    0m0.128s
user    0m0.096s
sys     0m0.014s
Hence, an iteration (including table setup) takes at most 24ns (36 cycles). Clearly, memory access is the bottleneck for larger p values. As you have seen before, the average time per residue class climbs up to 160ns for p around 2^31.

On the other hand, on-the-fly computation of Jacobi symbols, as well as the rest of the iteration, can be carried out in registers alone (at least on the PowerPC). Now that would be nice: No memory consumption, and no CPU idling.

However, my current code for the "binary" approach to Jacobi symbol computation needs about 6 cycles per bit of the Jacobi symbol operands (2x32) which at 1.5 GHz results in about 250ns per Jacobi symbol, thus more than 500ns per iteration. That is discouraging. For the time being, I recommend using the table-based version I already posted.
ccorn is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Antipodean arithmetic ewmayer Science & Technology 34 2015-10-03 01:31
Some arithmetic... science_man_88 science_man_88 11 2014-07-30 22:53
modular arithmetic science_man_88 Miscellaneous Math 42 2011-07-26 02:02
Simple Arithmetic! mfgoode Puzzles 82 2007-05-02 08:13
Easy Arithmetic davar55 Puzzles 6 2007-03-20 17:47

All times are UTC. The time now is 10:26.

Wed Sep 30 10:26:55 UTC 2020 up 20 days, 7:37, 0 users, load averages: 1.30, 1.47, 1.41

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.