Karim Belabas on Wed, 01 Mar 2017 17:56:06 +0100

 Re: Mathematica "Reduce" function

• To: pari-users@pari.math.u-bordeaux.fr
• Subject: Re: Mathematica "Reduce" function
• From: Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>
• Date: Wed, 1 Mar 2017 17:55:56 +0100
• Delivery-date: Wed, 01 Mar 2017 17:56:07 +0100
• Dkim-signature: v=1; a=rsa-sha256; c=simple/simple; d=math.u-bordeaux.fr; s=mail; t=1488387358; bh=FrPqNALHs6jpWX81x/Nhj58TizuBEONJaKibCNHm/dc=; h=Date:From:To:Subject:References:In-Reply-To:From; b=P9gSqmBg+dDFTr52P4GPbR+NswSc5JY/+R2xAiuEn6Y+zD2qoWRMGx/vKzMLyPYzC aOKhrwZ6jwZhukrgweC/A1EQ5LwdW/r4uStQQMs9ml0JF5yau6uKxe6LFKdVc+wGz7 yGTKgzoDtYlArX8QvFPV7pUalwVCrCZCH3mkx5DY=
• Mail-followup-to: pari-users@pari.math.u-bordeaux.fr
• References: <20170301164507.GK1825@MBP-pfortuny.local>
• User-agent: Mutt/1.6.0 (2016-04-01)

```* 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]
`

```