mersenneforum.org Compositions of arithmetic progressions
 Register FAQ Search Today's Posts Mark Forums Read

 2008-11-11, 02:38 #1 jasonp Tribal Bullet     Oct 2004 2×3×19×31 Posts Compositions of arithmetic progressions So this has now come up several times in the course of building msieve code, and it's high time I tried to understand how to think about it. Suppose you have two arithmetic progressions, r1 + k1 * p1 and r2 + k2 * p2. If p1 and p2 are coprime, how does one go about constructing a third arithmetic progression P = r3 + k3 * p1 whose members all lie on values of the p2 progression? Put another way, k3 is a multiple of p2, so that P maps the first progression onto the lattice formed by the second. I know that when r2 is zero, then r3 is r1 * modinverse(p2,p1) mod p1, where modinverse(x,y) is the modular inverse of x modulo y. What I don't understand is how to generalize this to the case of arbitrary r2. Apologies if this is too basic. The case when p1 and p2 share factors is also of interest, though less so.
2008-11-11, 11:35   #2
R.D. Silverman

Nov 2003

746010 Posts

Quote:
 Originally Posted by jasonp So this has now come up several times in the course of building msieve code, and it's high time I tried to understand how to think about it. Suppose you have two arithmetic progressions, r1 + k1 * p1 and r2 + k2 * p2. If p1 and p2 are coprime, how does one go about constructing a third arithmetic progression P = r3 + k3 * p1 whose members all lie on values of the p2 progression? Put another way, k3 is a multiple of p2, so that P maps the first progression onto the lattice formed by the second. I know that when r2 is zero, then r3 is r1 * modinverse(p2,p1) mod p1, where modinverse(x,y) is the modular inverse of x modulo y. What I don't understand is how to generalize this to the case of arbitrary r2. Apologies if this is too basic. The case when p1 and p2 share factors is also of interest, though less so.
If r1 + k_i p1 = r2 + m_i p2 for some (k_i, m_i), then trivially

r2-r1 + m_i p2 = 0 mod p1, whence m_i = [r1-r2] * p2^-1 mod p1

What else are you looking for? It's just a linear congruence.

 2008-11-11, 12:40 #3 jasonp Tribal Bullet     Oct 2004 1101110011102 Posts Well the problem is trivial when you phrase it that way :) Makes perfect sense, thanks.
2010-01-22, 19:49   #5
maxal

Feb 2005

22×32×7 Posts

Quote:
 Originally Posted by jasonp So how does one compute a basis for the intersection of two shifted 3x3 lattices?
If I got the problem correctly, you need first to find a common shift S by solving a system of congruences (using CRT):
S == R0_1 (mod p_1^{k_1})
S == R0_2 (mod p_2^{k_2})
...
with respect to S.
Then you rewrite you matrix equation as:
Code:
| C - S |   | p^k  -r_i  -r_i^2 | | i |
|   Y   | = |  0     1      0   | | j |
|   Z   |   |  0     0      1   | | k |
(where C,Y,Z,S are the same for all p^k) and proceed as if there were no shifts at all.

 2011-08-19, 16:09 #6 jasonp Tribal Bullet     Oct 2004 DCE16 Posts I might as well make this thread the dumping ground for all the problems I have with arithmetic progressions. Here's the latest, a consequence of an insidious bug in msieve that I'm trying to fix: Suppose you have a bunch of different arithmetic progressions R0 + i * p^k where p is prime and p^k is small (say less than 1000). There are lots of different R0, up to p^k of them. I need to 'map' each of these progressions onto a lattice of size L, i.e. to find another arithmetic progression R0' + j * p^k such that every value of that second progression lies on a lattice A + m * L. When L and p^k are coprime this is easy, and was addressed by Bob's post above. In fact with many R0 you can find R0' via a single table lookup: maintain an array of size p^k and put j at location (A+j*L) mod p^k for each j in turn, so that R0' = table[R0]. What I evidently don't understand is what to do when p divides L one or more times. I originally assumed that the table lookup method described above still works, except that - R0' may not exist depending on the precise value of A and L - the new progression would have a step value of p^k / gcd(L, p^k) and not p^k but I've noticed numerical examples where that's not true. Rather than trying to fit a heuristic to data, I was wondering how to solve this (embarrassingly easy sounding) problem analytically.
2011-08-20, 08:26   #7
axn

Jun 2003

2·32·269 Posts

Quote:
 Originally Posted by jasonp - the new progression would have a step value of p^k / gcd(L, p^k) and not p^k
Wouldn't the step value be LCM(p^k, L)= L* p^k / gcd(L, p^k) ? What am I missing?

 2011-08-20, 09:01 #8 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 1,429 Posts The complete solution is known from Number Theory, see: To find the same terms of two arithmetic progressions of: r1+x*n1 r2+y*n2 (In your case n1=p^k, n2=L) Suppose that: r1+x*n1=r2+y*n2, from this r1+x*n1==r2 mod n2 x*n1==r2-r1 mod n2 This is solvable if and only if gcd(n1,n2)|(r2-r1) and in this case divide by gcd(n1,n2), you get: x*n1/gcd(n1,n2)==(r2-r1)/gcd(n1,n2) mod n2/gcd(n1,n2) and here gcd(n1/gcd(n1,n2),n2/gcd(n1,n2))=1 so this system is solvable. And there is exaclty one solution mod n2/gcd(n1,n2) Last fiddled with by R. Gerbicz on 2011-08-20 at 09:03
 2011-08-20, 13:42 #9 jasonp Tribal Bullet     Oct 2004 2·3·19·31 Posts Thanks, makes sense. axn: You'd be correct that that's the step value in 'normal' coordinates, but I'm looking for the step value in 'lattice' coordinates. The sieving procedure I'm trying to fix starts off with lattice points, and then converts back whatever good lattice points that it finds.

 Similar Threads Thread Thread Starter Forum Replies Last Post MattcAnderson MattcAnderson 28 2017-05-08 20:58 maxal Software 18 2010-10-04 17:11 grandpascorpion Math 18 2007-03-28 15:08 Xyzzy Math 11 2004-12-17 17:00 Annunaki Math 37 2003-07-26 15:19

All times are UTC. The time now is 15:13.

Mon Jan 18 15:13:06 UTC 2021 up 46 days, 11:24, 0 users, load averages: 2.42, 2.51, 2.53