About Polyhedron

[Juan Grados]

 Dear members,

I am trying to reproduce page 9 of https://eprint.iacr.org/2016/407.pdf but until now is not possible to find the 65 inequalities that paper says. I am thinking that maybe this is because the version of SAGE I am using (this is 9). Do you think that there is any chance to obtain 65 inequalities using P.Hrepresentation() in other version of SAGE?

from sage.all import *
 vertices = [i for i in range(2**6)]
 vertices_to_drop = []
 def eq(x, y, z):
     if (x == y and y == z):
         return 1
     return 0
 for j in range(2**6):
     if ((((j>>5)&1) == ((j>>4)&1) and ((j>>4)&1) == ((j>>3)&1)) and (((j>>3)&1) != (((j>>2)&1) ^ ((j>>1)&1) ^ ((j>>0)&1)))):
         vertices_to_drop.append(j);
 possible_patterns = list(set(vertices) - set(vertices_to_drop))
 print(possible_patterns)
 possible_patterns_vector = []
 for num in possible_patterns:
      possible_patterns_vector.append([int(n) for n in bin(num)[2:].zfill(6)] + [eq(((num>>5)&1), ((num>>4)&1), ((num>>3)&1)) ^ 1])
 print(possible_patterns_vector[0])
 print(possible_patterns_vector[1])
 P = Polyhedron(vertices = possible_patterns_vector)
 for h in P.Hrepresentation():
    print(h)

---------------------------------------------------------------------
D.Sc. Juan del Carmen Grados Vásquez
Laboratório Nacional de Computação Científica 
Tel: +55 21 97633 3228

(http://www.lncc.br/)
http://juaninf.blogspot.com
---------------------------------------------------------------------

[Vincent Delecroix]

Dear Juan,

With sage 9.2 I obtain very quickly the output

An inequality (-1, -1, -1, 0, 0, 0, 1) x + 2 >= 0
An inequality (0, -1, 0, 0, 0, 0, 0) x + 1 >= 0
An inequality (-1, 0, 0, 0, 0, 0, 0) x + 1 >= 0
An inequality (0, 0, -1, 0, 0, 0, 0) x + 1 >= 0
An inequality (-1, 1, 0, 0, 0, 0, -1) x + 1 >= 0
An inequality (-1, 0, 1, 0, 0, 0, -1) x + 1 >= 0
An inequality (0, -1, 1, 0, 0, 0, -1) x + 1 >= 0
An inequality (0, 1, -1, 0, 0, 0, -1) x + 1 >= 0
An inequality (1, -1, 0, 0, 0, 0, -1) x + 1 >= 0
An inequality (1, 0, -1, 0, 0, 0, -1) x + 1 >= 0
An inequality (1, 1, 1, -3, 0, 0, -2) x + 2 >= 0
An inequality (0, 0, 1, -1, 0, 0, -1) x + 1 >= 0
An inequality (1, 0, 0, -1, 0, 0, -1) x + 1 >= 0
An inequality (0, 0, 0, -1, 0, 0, 0) x + 1 >= 0
An inequality (0, 1, 0, -1, 0, 0, -1) x + 1 >= 0
An inequality (0, 0, 0, 0, -1, 0, 0) x + 1 >= 0
An inequality (0, 0, 0, 0, 0, -1, 0) x + 1 >= 0
An inequality (0, 0, -1, 1, -1, 0, -1) x + 2 >= 0
An inequality (-1, 0, 0, 1, -1, 0, -1) x + 2 >= 0
An inequality (0, -1, 0, 1, -1, 0, -1) x + 2 >= 0
An inequality (-1, -1, -1, 3, -3, 0, -2) x + 5 >= 0
An inequality (1, 1, 1, 0, 0, 0, 1) x - 1 >= 0
An inequality (0, 0, 1, 0, 0, 0, 0) x + 0 >= 0
An inequality (0, 0, 0, 1, 0, 0, 0) x + 0 >= 0
An inequality (0, 0, 1, 0, 1, -1, -1) x + 1 >= 0
An inequality (0, 1, 0, 0, 1, -1, -1) x + 1 >= 0
An inequality (1, 1, 1, 0, 3, -3, -2) x + 2 >= 0
An inequality (-1, -1, -1, 3, 0, 3, -2) x + 2 >= 0
An inequality (0, 1, 0, 0, 0, 0, 0) x + 0 >= 0
An inequality (1, 0, 0, 0, 1, -1, -1) x + 1 >= 0
An inequality (0, 0, 0, 0, 0, 0, 1) x + 0 >= 0
An inequality (1, 0, 0, 0, 0, 0, 0) x + 0 >= 0
An inequality (0, 0, 0, 0, 1, 0, 0) x + 0 >= 0
An inequality (0, 0, 0, 0, 0, 1, 0) x + 0 >= 0
An inequality (0, -1, 0, 1, 0, 1, -1) x + 1 >= 0
An inequality (-1, 0, 0, 1, 0, 1, -1) x + 1 >= 0
An inequality (0, 0, -1, 1, 0, 1, -1) x + 1 >= 0

You should describe more precisely what is the problem with your
version 9. What is not working with the code?

Best regards,
Vincent

[Vincent Delecroix]

Note that these are 37 inequalities and not 65.

[Juan Grados]

Yes, but according to that paper it will be 65, and not 37. The paper is from 2016, maybe with an older SAGE version I get 65?. I tried version 7 and also I obtained 37.

---------------------------------------------------------------------
D.Sc. Juan del Carmen Grados Vásquez
Laboratório Nacional de Computação Científica 
Tel: +55 21 97633 3228

(http://www.lncc.br/)
http://juaninf.blogspot.com
---------------------------------------------------------------------

--
You received this message because you are subscribed to the Google Groups "sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/a5e68912-24fb-b598-1311-04350e2251a6%40gmail.com.

[Juan Grados]

Maybe you know some sage with an older version online, in my computer I am only able to install 7 using docker, but it seems that there are no more older docker sage versions? 

---------------------------------------------------------------------
D.Sc. Juan del Carmen Grados Vásquez
Laboratório Nacional de Computação Científica 
Tel: +55 21 97633 3228

(http://www.lncc.br/)
http://juaninf.blogspot.com
---------------------------------------------------------------------

[Emmanuel Charpentier]

Are those 65 inequalities independent ? For example

```

x+y<5

x+y<3

```

are distinct, but only the second defines the solution : the first is implied by the second...

Could you check the independence of the 65 inequalities in the paper ? For example, you may try to solve the system of 65 inequalities of the paper, and see if (a newer version of) sage is able to reduce it.

HTH,

[Juan Grados]

Thanks you to reply. The paper does not show the equations.

---------------------------------------------------------------------
D.Sc. Juan del Carmen Grados Vásquez
Laboratório Nacional de Computação Científica 
Tel: +55 21 97633 3228

(http://www.lncc.br/)
http://juaninf.blogspot.com
---------------------------------------------------------------------

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/6e9c9a52-00a4-4c82-8e2f-2866a4ff9dean%40googlegroups.com.

[Juan Grados]

Dear members of support,

I think I managed to solve this question. That is after apply an algorithm I found the same quantity of inequalities the authors claims -- 13 inequalities. But now, I would like to know if any one of you see any relation between the autoher inequalities and sage inequalities

These are the sage inequalities

An inequality (1, 0, -1, 0, 0, 0, 1) x + 0 >= 0
An inequality (0, -1, 1, 0, 0, 0, 1) x + 0 >= 0
An inequality (-1, 1, 0, 0, 0, 0, 1) x + 0 >= 0
An inequality (-1, -1, -1, 0, 0, 0, -1) x + 3 >= 0
An inequality (1, 1, 1, 0, 0, 0, -1) x + 0 >= 0
An inequality (1, 1, 1, -3, -3, -3, 2) x + 6 >= 0
An inequality (-1, -1, -1, 3, -3, -3, 2) x + 6 >= 0
An inequality (-1, -1, -1, -3, 3, -3, 2) x + 6 >= 0
An inequality (-1, -1, -1, -3, -3, 3, 2) x + 6 >= 0
An inequality (1, 1, 1, 3, 3, -3, 2) x + 0 >= 0
An inequality (1, 1, 1, 3, -3, 3, 2) x + 0 >= 0
An inequality (1, 1, 1, -3, 3, 3, 2) x + 0 >= 0
An inequality (0, 0, -1, 1, 1, 1, 1) x + 0 >= 0

And those are the authors inequalities

β[i]−γ[i] + (¬eq(α[i],β[i], γ[i])) ≥ 0,
α[i]−β[i] + (¬eq(α[i],β[i], γ[i])) ≥ 0,
−α[i] +γ[i] + (¬eq(α[i],β[i], γ[i])) ≥ 0,
−α[i]−β[i]−γ[i]−(¬eq(α[i],β[i], γ[i])) ≥ −3,
α[i] +β[i] +γ[i]−(¬eq(α[i],β[i], γ[i])) ≥ 0,
−β[i] +α[i+1] +β[i+1] +γ[i+1] + (¬eq(α[i],β[i], γ[i])) ≥ 0,
β[i] +α[i+1]−β[i+1] +γ[i+1] + (¬eq(α[i],β[i], γ[i])) ≥ 0,
β[i]−α[i+1] +β[i+1] +γ[i+1] + (¬eq(α[i],β[i], γ[i])) ≥ 0,
α[i] +α[i+1] +β[i+1]−γ[i+1] + (¬eq(α[i],β[i], γ[i])) ≥ 0,
γ[i]−α[i+1]−β[i+1]−γ[i+1] + (¬eq(α[i],β[i], γ[i])) ≥ −2,
−β[i] +α[i+1]−β[i+1]−γ[i+1] + (¬eq(α[i],β[i], γ[i])) ≥ −2,
−β[i]−α[i+1] +β[i+1]−γ[i+1] + (¬eq(α[i],β[i], γ[i])) ≥ −2,
−β[i]−α[i+1]−β[i+1] +γ[i+1] + (¬eq(α[i],β[i], γ[i])) ≥ −2

The vertices has the following form (α[i], β[i], γ[i], α[i+1], β[i+1], γ[i+1], (¬eq(α[i],β[i], γ[i]))

---------------------------------------------------------------------
D.Sc. Juan del Carmen Grados Vásquez
Laboratório Nacional de Computação Científica 
Tel: +55 21 97633 3228

(http://www.lncc.br/)
http://juaninf.blogspot.com
---------------------------------------------------------------------