mersenneforum.org > Math An arithmetic permutation
 Register FAQ Search Today's Posts Mark Forums Read

 2009-05-10, 23:07 #1 Dougy     Aug 2004 Melbourne, Australia 23·19 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} 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$.
2009-05-11, 11:55   #2
R.D. Silverman

Nov 2003

1C4016 Posts

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.

2009-05-11, 12:14   #3
Chris Card

Aug 2004

8216 Posts

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

2009-05-11, 12:25   #4
maxal

Feb 2005

22×32×7 Posts

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

Last fiddled with by maxal on 2009-05-11 at 12:26

 2009-05-12, 21:37 #5 Dougy     Aug 2004 Melbourne, Australia 23×19 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 22·37 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.
2010-06-01, 17:23   #7
davieddy

"Lucan"
Dec 2006
England

144638 Posts

Quote:
 Originally Posted by Dougy This problem was proposed by Ian Wanless.
I used to teach him at St Paul's Skool. Smart guy!

2010-06-13, 00:39   #8
ccorn

Apr 2010

22·37 Posts
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
 arithperm.zip (3.8 KB, 68 views)

 2010-06-17, 22:01 #9 ccorn     Apr 2010 22×37 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 ewmayer Science & Technology 34 2015-10-03 01:31 science_man_88 science_man_88 11 2014-07-30 22:53 science_man_88 Miscellaneous Math 42 2011-07-26 02:02 mfgoode Puzzles 82 2007-05-02 08:13 davar55 Puzzles 6 2007-03-20 17:47

All times are UTC. The time now is 14:08.

Sat Oct 31 14:08:31 UTC 2020 up 51 days, 11:19, 2 users, load averages: 2.93, 2.77, 2.61