Re: Mathematica "Reduce" function

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Wed, Mar 01, 2017 at 05:45:07PM +0100, Pedro Fortuny Ayuso wrote:
> Hi,

Hello Pedro,
 
> In Mathematica, you can do
> 
> In[1]:=	
> Reduce[x^2 + 3 y^2 == 4 && 3 x^3 - 4 y^2 + x y == 1, {x, y}, Modulus -> 9]
> 
> Out[1]=	...

What is the expected output ?

> To get a list of the solutions of polynomial equations over Z/qZ (in
> the above example, over Z/9Z).

You can do

? [[x,y]|x<-[0..8];y<-[0..8],x^2 + 3*y^2 == Mod(4,9) && 3*x^3 - 4*y^2 + x*y == Mod(1,9)]
%1 = [[8,1],[8,4],[8,7]]

Is it what you have in mind ?

> I am trying to count the solutions of some 3-variable polynomial
> over Z/(2^k)Z for different k, but the naive approach of looking
> at all the points is (obviously) infeasible.

There are much better ways. First you should use elimination theory
to reduce the problem to non singular curves and then use p-adic
lifting, but this is not easy to do in PARI.

In your example, you can use polresultant:

? P=polresultant(x^2 + 3*y^2 -4, 3*x^3 - 4*y^2 + x*y-1)
%7 = 243*y^6-54*y^5-953*y^4+144*y^3+1300*y^2-96*y-575
so if [x,y] is a solution, then 
243*y^6-54*y^5-953*y^4+144*y^3+1300*y^2-96*y-575 = 0
then
? polrootspadic(P,3,10)
%2 = []~

Cheers,
Bill.