Re: Mathematica "Reduce" function

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* Pedro Fortuny Ayuso [2017-03-01 17:45]:
> Hi,
> 
> 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]=	...
> 
> To get a list of the solutions of polynomial equations over Z/qZ (in
> the above example, over Z/9Z).
> 
> Is this possible in pari?

Not in this generality. You can only do it via exhaustive enumeration.

If you restrict to solutions over *fields* then polresultant() allows
to eliminate variables

(17:51) gp > polresultant(x^2+3*y^2-4, 3*x^3 - 4*y^2 + x*y - 1, y)
%1 = 81*x^6 + 72*x^5 + 19*x^4 - 342*x^3 - 164*x^2 + 361

(Any x that's part of solution (x,y) of the original 2 equations is a
root of that polynomial; assuming we look in a field of characteristic != 3)


Even for roots mod powers of a prime p, the existing functions have a
different semantic: they tell you whant happens in Q_p and give you the
result mod p^r...

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

It need not be infeasible: 2^{3k} possibilities ... (But looking for
local points in (Q_2)^3 is going to be much easier.)

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 21 23
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`