Error in I.variety(algorithm='msolve', proof=False)

[Peter Mueller]

R.<a, b> = GF(2)[]
L = [a^2+a, b^2+b]
I = ideal(L)
V = I.variety(algorithm='msolve', proof=False)

raises a `ValueError: positive-dimensional ideal`, which of course is nonsense. Exporting the system to an msolve-readable file and using msolve directly (with the -P 2 flag) returns the correct result.

So this does not seem to be an msolve bug, but probably a Sage error in parsing the msolve output. (My system msolve has version 0.6.6-1, but the same happened with 0.6.5).

My SageMath version is 10.4.rc1. With Sage 10.3,  this examples raises a `NotImplementedError: characteristic 2 too small`.

So it seems that for the time being, one has to write one's own interface to msolve :-(

-- Peter Mueller

[Marc Mezzarobba]

'Peter Mueller' via sage-devel wrote:
> R.<a, b> = GF(2)[]
> L = [a^2+a, b^2+b]
> I = ideal(L)
> V = I.variety(algorithm='msolve', proof=False)
>
> raises a `ValueError: positive-dimensional ideal`, which of course is
> nonsense. Exporting the system to an msolve-readable file and using
> msolve directly (with the -P 2 flag) returns the correct result.

What exact command are you using to run msolve, and what does your input
file contain? On my system:

~$ cat /tmp/tmprcz_zw9l
a,b
2
a^2+a,
b^2+b
~$ msolve -P 2 -f /tmp/tmprcz_zw9l
[1, 3, -1, []]:

--
Marc

[Peter Mueller]

msolve apparently ignores the last line of the input file if it does not end with a newline character. If one adds it, then it yields the correct result. The doc of msolve ("2 Input file format") probably should be clearer about that.

I guess that in your snippet, you manually typed the `enter` key after the `cat` command in the console.

-- Peter Mueller

[Marc Mezzarobba]

'Peter Mueller' via sage-devel wrote:
> I guess that in your snippet, you manually typed the `enter` key after
> the `cat` command in the console.

Hmm, no, there is a newline at the end:

~$ hexdump -c /tmp/tmprcz_zw9l
0000000 a , b \n 2 \n a ^ 2 + a , \n b ^ 2
0000010 + b \n
0000013

--
Marc

[Peter Mueller]

OK, it apparently was a bug of the previous version of msolve: For `msolve -P 2 -f file.ms` with msolve 0.6.5-2 yields the wrong result claiming that the dimension is positive, no matter whether file.ms ends with a newline character or or not, while msolve 0.6.6-1 yields the correct result in both cases. Still, from within Sage, I get the wrong result. So I guess I need to force Sage to use the system msolve rather the one which Sage built during installation.

-- Peter Mueller

[Dima Pasechnik]

On Sun, Jun 30, 2024 at 12:08 PM 'Peter Mueller' via sage-devel
<sage-...@googlegroups.com> wrote:
>
> OK, it apparently was a bug of the previous version of msolve: For `msolve -P 2 -f file.ms` with msolve 0.6.5-2 yields the wrong result claiming that the dimension is positive, no matter whether file.ms ends with a newline character or or not, while msolve 0.6.6-1 yields the correct result in both cases. Still, from within Sage, I get the wrong result. So I guess I need to force Sage to use the system msolve rather the one which Sage built during installation.

Yes. For the time being you can symlink local/bin/msolve to your system msolve

I.e.

rm local/bin/msolve
ln -s `which msolve` local/bin/msolve

We need to work on https://github.com/sagemath/sage/issues/38315
to fix this properly

>
> -- Peter Mueller
>
> Marc Mezzarobba schrieb am Sonntag, 30. Juni 2024 um 12:27:25 UTC+2:
>>
>> 'Peter Mueller' via sage-devel wrote:
>> > I guess that in your snippet, you manually typed the `enter` key after
>> > the `cat` command in the console.
>>
>> Hmm, no, there is a newline at the end:
>>
>> ~$ hexdump -c /tmp/tmprcz_zw9l
>> 0000000 a , b \n 2 \n a ^ 2 + a , \n b ^ 2
>> 0000010 + b \n
>> 0000013
>>
>> --
>> Marc
>>

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/848baa32-eb93-4bd7-9b7f-b3b06901b5c8n%40googlegroups.com.

[Dima Pasechnik]

Hi Marc,

On Sun, Jun 30, 2024 at 8:04 AM Marc Mezzarobba <ma...@mezzarobba.net> wrote:
>
> 'Peter Mueller' via sage-devel wrote:
> > R.<a, b> = GF(2)[]
> > L = [a^2+a, b^2+b]
> > I = ideal(L)
> > V = I.variety(algorithm='msolve', proof=False)
> >
> > raises a `ValueError: positive-dimensional ideal`, which of course is
> > nonsense. Exporting the system to an msolve-readable file and using
> > msolve directly (with the -P 2 flag) returns the correct result.

with an up to date
(latest msolve
commit a286a83057b3ac2dab5b660af92b1412d66ecf9b (HEAD, origin/master,
origin/HEAD)
Merge: dd6a447 f109dd5
Author: ederc <ed...@mathematik.uni-kl.de>
Date: Fri Jun 28 22:12:17 2024 +0200)

I am getting "NotImplementedError"

sage: R.<a, b> = GF(2)[]
....: L = [a^2+a, b^2+b]
....: I = ideal(L)
....: V = I.variety(algorithm='msolve', proof=False)
---------------------------------------------------------------------------
NotImplementedError Traceback (most recent call last)
Cell In[1], line 4
2 L = [a**Integer(2)+a, b**Integer(2)+b]
3 I = ideal(L)
----> 4 V = I.variety(algorithm='msolve', proof=False)
[...]
File /mnt/opt/Sage/sage-dev/src/sage/rings/polynomial/msolve.py:282,
in variety(ideal, ring, proof)
278 # Criterion suggested by Mohab Safey El Din to avoid cases where there
279 # is no rational parameterization or where the one returned by msolve
280 # has a significant probability of being incorrect.
281 if deg >= char > 0 or 0 < char <= 2**17 and deg != elim.degree():
--> 282 raise NotImplementedError(f"characteristic {char} too small")
283 den = to_poly(den)

So this is due to "0 < char <= 2**17 and deg != elim.degree()" - added
by you - which does not make sense to me.
Is this "Criterion" no longer applicable?

>
> What exact command are you using to run msolve, and what does your input
> file contain? On my system:
>
> ~$ cat /tmp/tmprcz_zw9l
> a,b
> 2
> a^2+a,
> b^2+b
> ~$ msolve -P 2 -f /tmp/tmprcz_zw9l
> [1, 3, -1, []]:

I am getting the following output:
[0, [2,
3,
4,
['a', 'b', 'A'],
[-1,-1,1],
[1,
[[1,
[1, 1]],
[0,
[1]],
[
[[-1,
[0]]],
[[0,
[1]]]
]]]]]:

[Marc Mezzarobba]

Hi Dima,

Dima Pasechnik wrote:
> So this is due to "0 < char <= 2**17 and deg != elim.degree()" - added
> by you - which does not make sense to me.
> Is this "Criterion" no longer applicable?

I don't know. This criterion was suggested to me by Mohab after I
complained that msolve -P 1 often returned nonsense in small
characteristic. (As far as I understand, there is always a tiny
probability that the output is incorrect, but at the time and in this
case the probability was not small at all.) I know the developers have
made many improvements since, but I don't know if this particular issue
is solved or not.

--
Marc

[Dima Pasechnik]

Given that on the input we discuss that answers returned by msolve don't make sense,
we should leave it in place.

IMHO msolve tries to find a univariate representation for the solutions, and so it needs a big field to work in - and I don't even know whether there any pitfalls with this approach for char>0.
(or char = 2, often the most pathological case)

Dima