An arithmetic permutation

Dougy · 2009-05-10, 23:07

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} 0 & 10 & 4 & 8 & 7 & 6 & 1 & 3 & 5 & 2 & 9 \\ 10 & 1 & 0 & 5 & 9 & 8 & 7 & 2 & 4 & 6 & 3 \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$ .

R.D. Silverman · 2009-05-11, 11:55

Quote:

Originally Posted by Dougy

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} 0 & 10 & 4 & 8 & 7 & 6 & 1 & 3 & 5 & 2 & 9 \\ 10 & 1 & 0 & 5 & 9 & 8 & 7 & 2 & 4 & 6 & 3 \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.

Chris Card · 2009-05-11, 12:14

Quote:

Originally Posted by R.D. Silverman

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

maxal · 2009-05-11, 12:25

Quote:

Originally Posted by R.D. Silverman

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$ .

Dougy · 2009-05-12, 21:37

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.

ccorn · 2010-05-30, 02:20

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.

davieddy · 2010-06-01, 17:23

Quote:

Originally Posted by Dougy

This problem was proposed by Ian Wanless.

I used to teach him at St Paul's Skool. Smart guy!

ccorn · 2010-06-13, 00:39

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.

ccorn · 2010-06-17, 22:01

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.

2009-05-10, 23:07	#1
Dougy Aug 2004 Melbourne, Australia 10011000₂ Posts	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$ .

2010-06-17, 22:01	#9
ccorn Apr 2010 2·3·5² Posts	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.

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

2009-05-12, 21:37	#5
Dougy Aug 2004 Melbourne, Australia 10011000₂ Posts	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.

2010-05-30, 02:20	#6
ccorn Apr 2010 2·3·5² Posts	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.