# Lifting bases for (Z/pZ)^n to Z^n

The following question came up in my research. I suspect that it has a slick answer, but I can't seem to find it.

Fix an integer n>=2 and a prime p. Define X(n) to be the set of primitive vectors in the Z-module Z^n and Y(n,p) to be the set of "lines" in the vector space (Z/pZ)^n (ie the spans of non-zero vectors). There is a natural surjective map f:X(n)-->Y(n,p) ("reduce mod p and take the span").

Question : Does there exist a map g:Y(n,p)-->X(n) with the following two properties.

1. f(g(L))=L for all L in Y(n,p).
2. If {L_1,...,L_n} \subset Y(n,p) spans the vector space (Z/pZ)^n, then {g(L_1),...,g(L_n)} is a basis for the Z-module Z^n.

Of course, I expect that the answer is no except in certain simple situations (for instance, it is yes for n=p=2), but I can't seem to find a proof.

EDIT : Oops! I phrased the question incorrectly. Above is a corrected version.

-
I realized what I did wrong around the same time that Scott and Steven did! Above is the "correct" version of the question. –  Andy Putman Oct 22 '09 at 2:45

Here's a unified argument based on my comments to Scott's post that doesn't use quadratic reciprocity in any form. Suppose n=2 and p >= 5, and lift each line of slope i in Y(2,p) to a point (ai+pbi, iai+pci).

Since each pair of lifts should give a basis of Z2 and thus a matrix with determinant \pm 1, taking each pair from among i=1,2,k+2 (with 1 <= k <= p-3) gives us conditions

a1a2 = \pm 1 (mod p)

k*a2ak+2 = \pm 1 (mod p)

(k+1)*a1ak+2 = \pm 1 (mod p).

Combining the first two gives ka22*a1ak+2 = \pm 1, or a22 = \pm(1+1/k) (mod p).

But for k=1 this gives us a22 = \pm 2, and for k=2 we get a22 = \pm (1 + (p+1)/2) = \pm (p+3)/2, so either (p+3)/2 = 2 (mod p) or (p+3)/2 = -2 (mod p). These imply p=1 and p=7, respectively, so already the only possible solution is p=7. But if p=7 then k=3 gives a22 = \pm 6, which is not \pm 2 (mod 7), so that doesn't work either. Thus a lift with n=2 can only possibly exist if p is 2 or 3.

-