My Math Forum Number of solutions modulo p squared

 Number Theory Number Theory Math Forum

 April 13th, 2011, 07:27 PM #1 Newbie   Joined: Mar 2011 Posts: 10 Thanks: 0 Number of solutions modulo p squared When we have a polynomial f(x) = 0 modulo $p_1p_2 \ldots p_k$ I know that using the Chinese Remainder Theorem, the maximum number of solutions is: the product of the maximum number of solutions for f(x) = 0 mod $p_i$. which is the degree of the polynomial f(x). then here we have at most k*deg(f) solutions However, in the case we are modulo $p^k$, I am wondering how I can find the maximum numbers of solutions for f(x) = 0 modulo $p^k$ ?
 April 13th, 2011, 07:55 PM #2 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: Number of solutions modulo p squared If p = 2 the maximum is 4. If p is an odd prime then the maximum is 2. Edit: Sorry, I'm thinking of a different problem here (square root mod p^k).
 April 13th, 2011, 09:38 PM #3 Senior Member   Joined: Oct 2008 Posts: 215 Thanks: 0 Re: Number of solutions modulo p squared To analysis f(x)=0(mod p^k) we could first find all solutions of f(x)=0(mod p). If all the solutions are x1,x2,...,xt, so we have f(x)=g(x)(x-x1)(x-x2)...(x-xt)(mod p) (Here some xi could be same) Any for any integer a, (g(a),p)=1. So p|f(a) iff p|(a-x1)(a-x2)...(a-xt) So p^k|f(a) => p|f(a)=>p|(a-x1)(a-x2)...(a-xt) => a = xi(mod p) for some i. Let f(x)-g(x)(x-x1)(x-x2)...(x-xt)=p*u(x) Now let's take a look for x=y*p+x1, if p^2|f(y*p+x1) so p^2|g(y*p+x1)*y*p*(y*p+x1-x2)...(y*p+x1-xt)+p*u(y*p+x1) so p|g(y*p+x1)*y*(y*p+x1-x2)...(y*p+x1-xt)+u(y*p+x1)=g(x1)*y*(x1-x2)...(x1-xt)+u(x1) so if x1 is different from x2,...,xt, We only have a unique y to reach the condition p^2|f(y*p+x1) And similiar, we could prove that there're exact t solutions for p^k|f(x) when x1,x2,...,xt are all different. But if any solutions are duplicated, such as x1=x2, it will be more complex For example, now p^2|f(y*p+x1) => p|u(x1). So either there're no correspondent solutions for p^2|f(y*p+x1) or all y are solutions. So in worse case, we may have p^{k-1} solutions. Such as if f(x)=(x-1)^k, for any a=1(mod p), p^k|f(a).
 April 17th, 2011, 02:24 PM #4 Newbie   Joined: Mar 2011 Posts: 10 Thanks: 0 Re: Number of solutions modulo p squared Actually I was looking for something simpler. For instance, consider a polynomial of degree 3 over Z/49Z. Since, $49=7^2$, then we consider first the solutions over Z/7Z. There are at most 3 solutions since the degree of the polynomial is 3. We want to lift these solutions to the ring Z/49Z. . My idea is then to use Hensel's lemma. The truth is that there are at most 8 solutions in Z/49Z. Why???
April 18th, 2011, 08:21 AM   #5
Senior Member

Joined: Sep 2008

Posts: 150
Thanks: 5

Re: Number of solutions modulo p squared

Hi all!

As this is a bit longer than intended here is the outline: I give the solution for the case k=2, then I give the prove of this solution, which gives a strong indication towards a formula in the general case. I give this formula (and the reasoning that leads to it) as a conjecture in the last paragraph.

Let me first make a remark, to fix the exact parameters of the problem:
I will assume that the coefficients of the polynomial are (p-adic) integers and look at them modulo different powers of p. In addition we should assume the polynomial to be normalized (i.e., leading coefficient=1), otherwise we get the maximal number of solutions:$p^k(x)=x$ is satisfied by all numbers mod $p^k$ and even if we assume the degree to be defined modulo p^k ( that would make the last example the zero polynomial) we could still take $p^{k-1}x=0$ which has degree one and $p^{k-1}$ solutions namely all multiples of p.

Quote:
 Originally Posted by fortin946 Actually I was looking for something simpler. For instance, consider a polynomial of degree 3 over Z/49Z. Since, $49=7^2$, then we consider first the solutions over Z/7Z. There are at most 3 solutions since the degree of the polynomial is 3. We want to lift these solutions to the ring Z/49Z. . My idea is then to use Hensel's lemma. The truth is that there are at most 8 solutions in Z/49Z. Why???
The short answer is: Because 8=7+1 and in general a polynomial of degree 3 will have at most p+1 solutions mod p^2. (Plus, there is allways one that has exactly this number, for instance $f(x)=x^2(x-1)$) more generally a polynomial of degree $d=2n$ has at most $n\cdot p$ solutions mod $p^2$ and one of degree $k=2n+1$ has at most $p\cdot n+1$ solutions. Moreover this number will allways be achieved provided p is big enough namely greater equal n in the first case and greater equal n+1 in the second place.

A proof of this statement actually involves Hensel's Lemma: First decompose your polynomial modulo p as $f(x)\equiv h(x)\cdot (x-a_1)^{n_1}\cdot ....\cdot (x-a_s)^{n_s} \text{ mod }p$ where all the $a_i$ are different mod p and h does not have any zero mod p. Now (the general version of) Hensel's lemma tells us, that we can find a factorization of f in $\mathbb{Z}_p[X]$ such that $f(x)=h(x)\cdot \prod g_i(x)$ and $g_i(x)\equiv (x-a_i)^{n_i} \text{ mod } p$. As all the elements of $\mathbb{Z}/p^k$ that do not map to zero in $\mathbb{Z}/p$ are units it is easy to check, that x is a zero of f mod $p^k$ iff it is a zero for some $g_i$ mod $p^k$. Thus we have reduced our problem to the case of the polynomials, which are powers of linear polynomials mod p.

I would have to think a bit more about the general case but it is clear, that a polynomial which is congruent to $(x-a)^n$ modulo p can have at most $p^{k-1}$ zeros mod p^k namely those numbers which are congruent to a modulo p. Conversely there are polynomials of this form, which have $p^{[k-k/n]}$ solutions (where [] is the floor function): simply take f(x)=(x-a)^n even before reducing mod p. This finishes the case, where k=2 as upper and lower bound agree for all $n\geq 2$ (and are in fact equal to p there) and for degree one polynomials we have always exactly one solution. So the best bet in the k=2 case is to take as many degree two factors as you can (each of which gives p zeros) and at most one smaller factor which is then of degree 1 and gives one additional zero.

Now in general i think, that $p^{[k-k/n]}$ is actually the best number of zeros you can get from one factor. And some combinatorics should show, that the best distribution, is to max out all the factors and have one for the rest. So writing $d=s\cdot k +r$ with s<r my conjecture is that there are at most $s\cdot p^{k-1} + p^{r-1}$ zeros mod p^k for a degree d polynomial and we get that many zeros for at least one polynomial as soon as p>s.

best rgds
Peter

 Tags modulo, number, solutions, squared

,

,

,

# polynomial modulo the square of a prime

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post scarecr0w132 Elementary Math 3 February 24th, 2014 08:19 AM FloorPlay Number Theory 2 October 30th, 2013 08:59 PM Bolt Algebra 7 July 31st, 2011 07:06 AM niravshah99 Number Theory 4 June 20th, 2010 02:53 AM earth Math Events 3 July 8th, 2009 09:14 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top