Ask Your Question

dan_fulea's profile - activity

2020-10-12 10:07:44 -0500 answered a question "how to test if two matrices are similar by a signed permutation matrix" code sage

I gave a detailed answer to a fuzzy question by Anonymous in the link below:

https://ask.sagemath.org/question/39515/how-to-find-the-permutation-matrix-associated-with-the-similarity-transformation-in-the-following-code/

(But compared to this question, the 39515 question qualifies as a detailed exposition.)

The steps would be:

  • check the characteristic polynoials, if there is no match, we can stop here.
  • build the eigenvalues, sort them somehow, if there is no match, stop here.
  • build the jordan decomposition and match the eigenvectors, allowing rescaling on the one side, and permutations of rows on the other side. A rough match can be done by first rescaling in the two Jordan base change matrices, so that the maximal absolute value occurs for the entry $1$ in each column.
2020-10-12 09:59:49 -0500 answered a question How to find the permutation matrix associated with the similarity transformation in the following code

Here is one more try to understand the situation. First of all, we will work over $\bar{\Bbb Q}$, and introduce the two matrices, $M,N$ to fix a notation with two similar letters:

v = i
F = QQbar
M = matrix( F, 6, 6,
            [  2,-1,-v, 0, 0, 0,
              -1, 2,-1, 0, 0, 0,
               v,-1, 3,-1, 0, 0,
               0, 0,-1, 2,-1, 0,
               0, 0, 0,-1, 2,-1,
               0, 0, 0, 0,-1, 1, ] )

N = matrix( F, 6, 6,
            [   2,-1, 0,-v, 0, 0,
               -1, 2,-1, 0, 0, 0,
                0,-1, 2,-1, 0, 0,
                v, 0,-1, 3, 0,-1,
                0, 0, 0, 0, 1,-1,
                0, 0, 0,-1,-1, 2, ] )

Then indeed, their characteristic polynomials coincide.

sage: M.charpoly()
x^6 - 12*x^5 + 53*x^4 - 106*x^3 + 94*x^2 - 30*x + 2
sage: N.charpoly()
x^6 - 12*x^5 + 53*x^4 - 106*x^3 + 94*x^2 - 30*x + 2
sage: N.charpoly() == N.charpoly()
True

We can ask for the Jordan normal form of each of the two matrices.

D, S = M.jordan_form(transformation=True)
E, T = N.jordan_form(transformation=True)

And note that the two diagonal matrices D and E coincide:

sage: D == E
True

We can print D, but to fit the result on this page, i will take the numerical approximation of D:

sage: D.n(30)
[0.089198758| 0.00000000| 0.00000000| 0.00000000| 0.00000000| 0.00000000]
[-----------+-----------+-----------+-----------+-----------+-----------]
[ 0.00000000| 0.47256641| 0.00000000| 0.00000000| 0.00000000| 0.00000000]
[-----------+-----------+-----------+-----------+-----------+-----------]
[ 0.00000000| 0.00000000|  1.3956621| 0.00000000| 0.00000000| 0.00000000]
[-----------+-----------+-----------+-----------+-----------+-----------]
[ 0.00000000| 0.00000000| 0.00000000|  2.3867094| 0.00000000| 0.00000000]
[-----------+-----------+-----------+-----------+-----------+-----------]
[ 0.00000000| 0.00000000| 0.00000000| 0.00000000|  3.1882644| 0.00000000]
[-----------+-----------+-----------+-----------+-----------+-----------]
[ 0.00000000| 0.00000000| 0.00000000| 0.00000000| 0.00000000|  4.4675990]

So the roots of the characteristic polynomials of M and N coincide, are real, and are placed on the diagonal above in increasing order. Note also: $$MS=SD\ ,\qquad NT=TD\ .$$ A check:

sage: bool(M*S == S*D)
True
sage: bool(N*T == T*D)
True

So far we have the equalities: $$ S^{-1}MS = D = T^{-1}NT\ . $$ The intertwiner $S$ between $M$ and $D$ is not unique, but it is unique up to multiplication with a diagonal matrix $Delta_S$. This is because of different eigenvalues on the diagonal. And of course, $D=Delta_SDDelta_S^{-1}$. So we can replace the above $S$ by $SDelta_S$, and this is the only freedom we have. The same holds "on the other side" with a diagonal matrix $Delta_T$. So, the "maximal freedom" we have is by writing $$ (SDelta_S)^{-1}M(SDelta_S) = D = (TDelta_T)^{-1}N(TDelta_T)\ . $$ We get rid of the expression $D$ "in the middle", and obtain the general form for an intertwiner: $$ (TDelta_T)(SDelta_S)^{-1}\ M\ (SDelta_S)(TDelta_T)^{-1} = N\ . $$ So we want to get a (signed - came in later) permutation matrix $P$ in: $$ (TDelta_T)(SDelta_S)^{-1}= P\ . $$ Equivalently: $$ TDelta_T= PSDelta_S\ . $$ We can arrange this (iff we can) with only one diagonal matrix $Delta$, $$ TDelta = PS\ . $$ The action of $Delta$ on $T$ is a renormalization of the column vectors.

The action of $P$ on $S$ is given by a row permutation. Such a row permutation also invariates the columns as a list. So we may want to compare the columns of $S$ and $T$. Numerically, the first column of $T$ and $S$ are:

T.columns()[0].n()
S.columns()[0].n()

Well, it is not so easy to keep order, so let us consider absolute values:

[ abs(entry) for entry in T.columns()[0].n() ]
[ abs(entry) for entry in S.columns()[0].n() ]

We obtain:

[1.00000000000000,
 0.953694040309665,
 1.00000000000000,
 1.11348300986965,
 1.50397481281530,
 1.36982212753272]

[1.00000000000000,
 1.00000000000000,
 1.22929314902987,
 1.80622358363301,
 2.22204111800645,
 2.43965534455263]

Again, we need a better strategy to match, so we divide by the maximal entry in the column in both cases.

sage: AS = [ max([ abs(e) for e in S.columns()[k] ]) for k in range(6) ]
sage: AT = [ max([ abs(e) for e in T.columns()[k] ]) for k in range(6) ]
sage: 
....:     [ abs(entry) / AT[0] for entry in T.columns()[0].n() ]
....:     [ abs(entry) / AS[0] for entry in S.columns()[0].n() ]
....: 

[0.664904752047072,
 0.634115699400868,
 0.664904752047072,
 0.740360144586006,
 1.00000000000000,
 0.910801242055735]

[0.409893964011287,
 0.409893964011287,
 0.503879841787769,
 0.740360144586006,
 0.910801242055736,
 1.00000000000000]

We expect a permutation of the values, but this is not the case. In this first column there are three entries that match each other, but the other three...

So we have a negative answer.


Note: Also the less structural brute force search leads to nothing.

sage: for p in SymmetricGroup(6):
....:     for d in cartesian_product([[+1, -1] for _ in range(6)]):
....:         D = diagonal_matrix(d)
....:         P = p.matrix()
....:         SP = S*P    # signed permutation
....:         if M*SP == SP*N:
....:             print(SD)

No result.

This note is here just to make clear which is the difference between an answer and an answer. The first answer is a good piece of work. (A lot to type and explain.) The second answer is close to run+copy+paste. It transposes also to questions, there is a big difference between a question and a question. In this case, more details would have been more than typing them. (Some people consider that giving details to the whole world would put every single individual researcher in the position to solve the problem on her or his own, then publish this the next day, than claim ownership of the result. This is never the case, we are in an other century, fluent information works best with pointed, complete information.)

2020-10-12 08:17:13 -0500 answered a question How is curve C(b) converted to elliptic curve?

I tried:

F.<b> = PolynomialRing(QQ)
R.<X,Y,Z> = PolynomialRing(F)
cubic = (3+b)*X^2*Y + (9+b)*X*Y^2 - (4+b)*X^2*Z + (3-b^2)*X*Y*Z + (-4+b)*Y^2*Z + (-9+b)*X*Z^2 + b*Y*Z^2
# fX, fY, fZ = WeierstrassForm(cubic, transformation=True)

WeierstrassForm(cubic)

This gives:

(-1/48*b^8 + 5/12*b^6 + 1/2*b^5 - 619/24*b^4 - 49/2*b^3 + 2755/12*b^2 - 2*b - 142345/48,
 1/864*b^12 - 5/144*b^10 - 1/24*b^9 + 223/96*b^8 + 59/24*b^7 - 2095/54*b^6 - 983/24*b^5 \
    + 27441/32*b^4 + 19765/24*b^3 - 863495/144*b^2 + 2213/6*b + 50223077/864)

(Result was manually rearranged.)

2020-10-12 08:08:40 -0500 edited question How is curve C(b) converted to elliptic curve?

How can we transform curve $$ C(b)\ :\ (3+b)X^2Y + (9+b)XY^2 - (4+b)X^2Z + (3-b^2)XYZ + (-4+b)Y^2Z + (-9+b)XZ^2+bYZ^2 $$ into an elliptic curve without valuing $b$?

Edited: Expression in code format:

(3+b)*X^2*Y + (9+b)*X*Y^2 - (4+b)*X^2*Z + (3-b^2)*X*Y*Z + (-4+b)*Y^2*Z + (-9+b)*X*Z^2 + b*Y*Z^2
2020-10-12 08:04:32 -0500 answered a question How to define algebra via generators and relations?

One possibility to implement the algebra $H_4$ from loc. cit., the one where we also use the relations $x^2=0$, $g^2=1$, $gx+xg=0$ (and there is no need for an inverse, since $g^{-1}=g$) would be:

A.<X,G> = FreeAlgebra(QQ, 2)    # or over QQbar
F = A.monoid()
X, G = F.gens()
monomials = [F(1), X, G, X*G]
MS = MatrixSpace(QQ, len(monomials))    # or respectively over QQbar

matrices = [
    # matrix showing the action of the first generator, X, on the monomials
    MS([0, 1, 0, 0,    # X*1 = X
          0, 0, 0, 0,    # X*X = 0
          0, 0, 0, 1,    # X*G = XG
          0, 0, 0, 0,    # X*XG = (XX)G = 0
         ]),
    # matrix showing the action of the second generator, G, on the monomials
    MS([0,  0, 1,  0,    # G*1 = G
          0,  0, 0, -1,    # G*X = -XG
          1,  0, 0,  0,    # G*G = 1
          0, -1, 0,  0,    # G*XG = (GX)G = (-XG)G=-X(GG)=-X
         ]),
]

H4.<x,g> = A.quotient(monomials, matrices)

Then we have for instance:

sage: (x+g)^2
1
sage: (1+x*g)^2
1
sage: (1+x+g)^10
512 + 512*x + 512*g

Note: It would be interesting to have a full working algebraic setting for the Hopf algebra $H_4$ (including $S$ and $\Delta$). Well, posting as anonymous is not a good idea in general, but ok, here is the state of the art so far.

2020-09-22 05:49:57 -0500 commented question SAGE_ROOT error when start the program

I suppose it is a linux install, the last error message is

Error setting environment variables by sourcing './sage-env'

so maybe one should look inside that ./sage-env. But this would be the start of the path. We need the same machine to debug the point of bad installation. Maybe some directories were removed. Try

sage -sh

then use set to see all environment variables. Here, DOT_SAGE may be the missing bridge. But there are many other reasons. Just reinstall. Which is the linux distro used?

2020-09-22 05:29:10 -0500 commented question Obtaining a group from distributive lattices

One can of course implement this group. It has a lot of elements, even if $K$ is finite, so the implementation depends on the needs. What should be done with this sage implementation? It is a good piece of work...

2020-09-04 21:42:14 -0500 answered a question Finding solution of expression with fractional power

We do not know what is sol, but i suppose it is the following...

sage: var('r');
sage: eq = 3*(2.2 + (64/r)^(1/3)) == 4*(2.2 + (128/(r-1))^(1/4))
sage: sol = solve(eq, r)
sage: sol
[r^(1/3) == 60*(r - 1)^(1/4)/(40*8^(1/4) + 11*(r - 1)^(1/4))]

It is clear that we cannot ask for the numerical value of sol[0].


Instead, we could help sage deliver the needed value. We just substitute $$ r = R^3 $$ and rewrite the given equation in the form: $$ \frac 34\left(\frac{22}{10} +\frac 4R\right)-\frac {22}{10} = \left(\frac {128}{R^3-1}\right)^{1/4}\ . $$ Rising both sides to the fourth power leads to a polynomial equation, which we can solve. We obtain one value of $R$, introduced by taking the fourth power. But it leads to no solution in $r$.

Try a plot of the difference to see there is no solution.

If there is some typo, then fix it, find an interval where the difference function changes the sign, then use gp-solve. (Inside pari or inside sage.)

2020-09-04 20:03:08 -0500 answered a question How to convert coordinates of a point from y^2=x^3+7 curve to y^2=x^3+4 curve?

The question is "not well defined" to have a mild answer.

Here i suppose that "converting" a point from one elliptic curve to an other one should be given by some structural map between the curves. However the two curves are not isomorphic. (There is also no map from one curve to the other one preserving the addition on both curves.) To see this let us observe some facts.

  • The curve $E_7$ given by the (affine) equation $y^2=x^3+7$ over $\Bbb F_p$, $p$ being the prime $p=2^{256}-2^{32}-977$, is known and related with the bitcoin avatar. Here is a link where we also have the order of $E(\Bbb F_p)$:

http://www.math.canterbury.ac.nz/~f.voloch/Pdfs/bittalk.pdf

  • This order is $N = 2^{256} - 432420386565659656852420866394968145599$.
  • This is a prime number. But it is not the order of the other curve from the OP, $E_4$ given by the (affine) equation $y^2=x^3+4$ over $\Bbb F_p$.

  • The following pieces of code support the above claims.

    p = 2^256 - 4294968273
    E4 = EllipticCurve(GF(p), [0, 4])
    E7 = EllipticCurve(GF(p), [0, 7])
    
    base_x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
    base_y = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
    
    P7 = E7.point( (base_x, base_y) )
    P4 = E4.random_point()
    
    N = 2^256 - 432420386565659656852420866394968145599
    NP7 = N*P7
    
    print(f"Is N prime? {N.is_prime()}")
    print(f"N * P7 = {NP7}")
    print("Is N * P4 = 0 on E4? {}".format(N*P4 == E4(0)))
    
  • The above delivers:

    Is N prime? True
    N * P7 = (0 : 1 : 0)
    Is N * P4 = 0 on E4? False
    
  • Note also the following:

    sage: E7.is_isomorphic(E4)
    False
    sage: E7.is_isogenous(E4)
    False
    

A final note, motivated by the question in:

https://crypto.stackexchange.com/questions/83542/how-to-convert-coordinates-o-a-point-from-y2-x37-to-y2-x34

(This question is also hard to understand, but it mentions the elliptic curves over the same field $\Bbb F_p$ with equations $y^2=x^3+k$ for "small" values of $k$, say $k=1,2,3,4$...)

Among these curves some are isomorphic to $E_7$. This happens for the following values of $k$:

sage: for k in range(1, 30):
....:     if E7.is_isomorphic(EllipticCurve(GF(p), [0, k])):
....:         print(k)
....: 
7
12
20
23
26
sage:

Note that these are exactly the values of $k$ such that there exists in the multiplicative group $\Bbb F_p^\times$ a root of order $6$ of the quotient $7/k$.

sage: for k in range(1, 30):
....:     v = GF(p)(k)/7
....:     print(f"{k}/7 has order {v.multiplicative_order().factor()}")
....: 
1/7 has order 2 * 3 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
2/7 has order 2 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
3/7 has order 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
4/7 has order 2 * 3 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
5/7 has order 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
6/7 has order 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
7/7 has order 1
8/7 has order 2 * 3 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
9/7 has order 2 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
10/7 has order 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
11/7 has order 2 * 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
12/7 has order 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
13/7 has order 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
14/7 has order 3 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
15/7 has order 2 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
16/7 has order 2 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
17/7 has order 2 * 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
18/7 has order 2 * 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
19/7 has order 2 * 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
20/7 has order 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
21/7 has order 2 * 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
22/7 has order 2 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
23/7 has order 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
24/7 has order 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
25/7 has order 2 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
26/7 has order 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
27/7 has order 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
28/7 has order 3 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
29/7 has order 2 * 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
sage:

(Exactly those $k$ lead to isomorphic curves for which the order of $k/7$ is lacking the factors $2$ and $3$.)

2020-09-04 18:01:26 -0500 commented question Can you solve a math problem: x+y=42, x-y=30?

Try something like:

sage: var('x,y');
sage: solve([x + y == 42, x - y == 30], [x, y])
[[x == 36, y == 6]]

(Or just ignore sage code, and use plain thoughts or simple drawings.)

2020-09-02 23:38:33 -0500 answered a question Rewriting linear combination of Groebner basis in terms of original terms

This answer ignores completely the Groebner basis. Just "lift" the corresponding element.

In an example:

R.<x,y,z> = QQ[]
f1, f2, f3 = (x + y + z)^2, x*y + y*z + z*x, x^3 + y^3 + z^3
J = R.ideal([f1, f2, f3])
h = x*y*z
print("Is h in J? {}".format(h in J))
q1, q2, q3 = h.lift(J)
print(f"q1 = {q1}\nq2 = {q2}\nq3 = {q3}")

This gives:

Is h in J? True
q1 = -1/3*x - 1/3*y - 1/3*z
q2 = x + y + z
q3 = 1/3

We have

sage: h == f1*q1 + f2*q2 + f3*q3
True

The line answering the question is q1, q2, q3 = h.lift(J).

2020-08-24 18:00:38 -0500 commented question How to find a element in elliptic curve ?(code added)

Please format sage / python code as code. For this, just indent all the code in some editor with 4 spaces or copy+paste it here, mark it, and while having it marked hit that button with the 101 and 010 on it. As it is, the question is not readable. It would be also a good idea to describe the objects you have first, then the "needed $x$" with given properties. Could you please edit the question to have a readable text?

2020-08-18 11:47:10 -0500 answered a question legendre_P(6,0) different evaluations

This is a partial answer, i have to submit now. (Maybe somebody can continue...)

The function legendre_P is "implemented" in sage by calling corresponding other function in other systems.

On my machine, asking in the sage interpreter for the help on this function gives:

Type:           Func_legendre_P
String form:    legendre_P
File:           /usr/lib/python3.8/site-packages/sage/functions/orthogonal_polys.py
Docstring:     
   EXAMPLES:

      sage: legendre_P(4, 2.0)
      55.3750000000000
      sage: legendre_P(1, x)
      x

and many further other lines. The line with the File: shows the location of the code, and the corresponding code is...

legendre_P = Func_legendre_P()

So we need Func_legendre_P instead, which is a class, and the constructor __init__ does the following job:

BuiltinFunction.__init__(self, 'legendre_P', nargs=2, latex_name=r"P",
                         conversions={'maxima':'legendre_p',
                                      'mathematica':'LegendreP',
                                      'maple':'LegendreP',
                                      'giac':'legendre'})

Now the maxima function legendre_p returns used for the conversion on my machine...

sage: maxima("legendre_p(6, 0);")
-5/16

And if we call the same function with the arguments 6 and x we get...

sage: maxima("legendre_p(6, x);")
(-21*(1-x))+(231*(1-x)^6)/16-(693*(1-x)^5)/8+(1575*(1-x)^4)/8-210*(1-x)^3+105*(1-x)^2+1
sage: p = (-21*(1-x))+(231*(1-x)^6)/16-(693*(1-x)^5)/8+(1575*(1-x)^4)/8-210*(1-x)^3+105*(1-x)^2+1
sage: p.subs({x:0})
-5/16
sage: p.subs(x=0)
-5/16

Now asking for the sage legendre_P in the same session leads to a crash. This is a good sign! (This depends on perspective. Well, it is good since it must be the case of a maxima collision...) In a new session:

sage: p = (-21*(1-x))+(231*(1-x)^6)/16-(693*(1-x)^5)/8+(1575*(1-x)^4)/8-210*(1-x)^3+105*(1-x)^2+1
sage: legendre_P(6, x)
231/16*x^6 - 315/16*x^4 + 105/16*x^2 - 5/16
sage: bool( p == legendre_P(6, x) )
True

So we have problems with

sage: legendre_P(6, 0)
5/16

Let's see which values are giving the difference:

sage: for k in [-10..10]:
....:     legendre_P6k, pk = legendre_P(6, k), p.subs(x=k)
....:     if legendre_P6k == pk:
....:         print(f"k = {k} :: same value {pk}")
....:     else:
....:         print(f"k = {k} :: different values {legendre_P6k} versus {pk}")
....: 
k = -10 :: same value 227860495/16
k = -9 :: same value 7544041
k = -8 :: same value 59271739/16
k = -7 :: same value 1651609
k = -6 :: same value 10373071/16
k = -5 :: same value 213445
k = -4 :: same value 867211/16
k = -3 :: same value 8989
k = -2 :: same value 10159/16
k = -1 :: same value 1
k = 0 :: different values 5/16 versus -5/16
k = 1 :: same value 1
k = 2 :: same value 10159/16
k = 3 :: same value 8989
k = 4 :: same value 867211/16
k = 5 :: same value 213445
k = 6 :: same value 10373071/16
k = 7 :: same value 1651609
k = 8 :: same value 59271739/16
k = 9 :: same value 7544041
k = 10 :: same value 227860495/16
sage:

OK, only the value 0 of the second argument leads to a difference, and the code was printing quickly the values for k from -10 to -1, then took a "long time" (2s maybe) to give me the false value for k = 0 then all the print was there.

I suspect a bad rerouting inside the classes
GinacFunction and BuiltinFunction, but i have to stop here the investigations.

2020-08-14 13:28:07 -0500 received badge  Nice Answer (source)
2020-08-14 11:03:38 -0500 answered a question Lusztig's a-function for the symmetric group via Sage

From the first definition in the OP, it is enough to compute the $a$-funcition on involutions. Here is a simple piece of code doing this in a verbose form for $S_3$, the group of permutations of the set ${1,2,3}$:

W = WeylGroup('A2', prefix='s')                                                                                                       
print(f"W = {W}")
print(f"W has order |W| = {W.order()}\n")

R.<q> = LaurentPolynomialRing(QQ)                                                                                                     
KL = KazhdanLusztigPolynomial(W, q)                                                                                                   
involutions = [w for w in W if w.order() in (1, 2)]

for w in involutions:
    lw = w.length()
    pw = KL.P( W(1), w )
    dw = pw.degree()
    aw = lw - 2*dw
    print(f"w = {w} = {w.to_permutation()} has:\n"
          f"l(w) = {lw}\n"
          f"d(w) = deg P(1,w) = deg( {pw} ) = {dw}\n"
          f"a(w) = l(w) - 2d(w) = {aw}\n")

Results:

W = Weyl Group of type ['A', 2] (as a matrix group acting on the ambient space)
W has order |W| = 6

w = 1 = (1, 2, 3) has:
l(w) = 0
d(w) = deg P(1,w) = deg( 1 ) = 0
a(w) = l(w) - 2d(w) = 0

w = s1 = (2, 1, 3) has:
l(w) = 1
d(w) = deg P(1,w) = deg( 1 ) = 0
a(w) = l(w) - 2d(w) = 1

w = s2 = (1, 3, 2) has:
l(w) = 1
d(w) = deg P(1,w) = deg( 1 ) = 0
a(w) = l(w) - 2d(w) = 1

w = s1*s2*s1 = (3, 2, 1) has:
l(w) = 3
d(w) = deg P(1,w) = deg( 1 ) = 0
a(w) = l(w) - 2d(w) = 3

(All K-L polynomials are trivial.) To do the same for the group $S_4$, using a less verbose output...

W = WeylGroup('A3', prefix='s')                                                                                                       
print(f"W = {W}")
print(f"W has order |W| = {W.order()}\n")

R.<q> = LaurentPolynomialRing(QQ)                                                                                                     
KL = KazhdanLusztigPolynomial(W, q)                                                                                                   
involutions = [w for w in W if w.order() in (1, 2)]

for w in involutions:
    lw = w.length()
    pw = KL.P( W(1), w )
    dw = pw.degree()
    aw = lw - 2*dw
    print(f"w = {w} = {w.to_permutation()} has:\n"
          f"a(w) = l(w) - 2d(w) = {lw} - 2deg({pw}) = {aw}\n")

Results:

W = Weyl Group of type ['A', 3] (as a matrix group acting on the ambient space)
W has order |W| = 24

w = 1 = (1, 2, 3, 4) has:
a(w) = l(w) - 2d(w) = 0 - 2deg(1) = 0

w = s3 = (1, 2, 4, 3) has:
a(w) = l(w) - 2d(w) = 1 - 2deg(1) = 1

w = s2 = (1, 3, 2, 4) has:
a(w) = l(w) - 2d(w) = 1 - 2deg(1) = 1

w = s2*s3*s2 = (1, 4, 3, 2) has:
a(w) = l(w) - 2d(w) = 3 - 2deg(1) = 3

w = s2*s3*s1*s2 = (3, 4, 1, 2) has:
a(w) = l(w) - 2d(w) = 4 - 2deg(1 + q) = 2

w = s1 = (2, 1, 3, 4) has:
a(w) = l(w) - 2d(w) = 1 - 2deg(1) = 1

w = s3*s1 = (2, 1, 4, 3) has:
a(w) = l(w) - 2d(w) = 2 - 2deg(1) = 2

w = s1*s2*s3*s2*s1 = (4, 2, 3, 1) has:
a(w) = l(w) - 2d(w) = 5 - 2deg(1 + q) = 3

w = s1*s2*s1 = (3, 2, 1, 4) has:
a(w) = l(w) - 2d(w) = 3 - 2deg(1) = 3

w = s1*s2*s3*s1*s2*s1 = (4, 3, 2, 1) has:
a(w) = l(w) - 2d(w) = 6 - 2deg(1) = 6

I would like to have the KL-cells inside sage, but i do not know how to get them now.

Personal note: There was some years ago the chance to use gap3+chevie, then make sage know about them, then get the corresponding information from chevie. Since gap4 i no longer use gap. After repeated switches between linux distros and linux reinstallations, i decided that it is simpler to rewrite all pieces of code inside chevie to be inside sage. But i need time and some support... maybe this could be a project for this year.


Let's try to get the same numbers using the RSK correspondence. The code results are also formatted to be printed in an array...

W = WeylGroup('A3', prefix='s')                                                                                                       
print(f"W = {W}")
print(f"W has order |W| = {W.order()}\n")


R.<q> = LaurentPolynomialRing(QQ)                                                                                                     
KL = KazhdanLusztigPolynomial(W, q)

def a_involution(w):
    lw = w.length()
    pw = KL.P( W(1), w )
    dw = pw.degree()
    aw = lw - 2*dw
    return aw

def a_page198(shape):
    return sum([binomial(entry, 2) for entry in shape])

def transposed_shape(shape):
    """this should be a basic method, but i could not find it...
    For the shape [3,2,2,1] we return [4,3,1] and conversely...

    [3,2,2,1] is     [4,3,1] is
    XXX              XXXX
    XX               XXX
    XX               X
    X
    """
    n = shape[0]
    return [len([rowlength for rowlength in shape if rowlength > k]) for k in range(n)]

for w in W:
    wp = w.to_permutation()
    Q = RSK( list(wp) )[1]
    sh = list(Q.shape())
    sht = transposed_shape(sh)
    if w.order() in (1, 2):
        a_inv = a_involution(w)
    else:
        a_inv = ''
    aw = a_page198(sht)
    print(r"{} & {} & {} & {} & {} & {} & {}\\\hline"
          .format(latex(w), wp, Q, sh, sht, a_inv, aw))

Results:

W = Weyl Group of type ['A', 2] (as a matrix group acting on the ambient space)
W has order |W| = 6

1 & (1, 2, 3) & [[1, 2, 3]] & [3] & [1, 1, 1] & 0 & 0\\\hline
s_{1}s_{2} & (2, 3, 1) & [[1, 2], [3]] & [2, 1] & [2, 1] &  & 1\\\hline
s_{2}s_{1} & (3, 1, 2) & [[1, 3], [2]] & [2, 1] & [2, 1] &  & 1\\\hline
s_{1} & (2, 1, 3) & [[1, 3], [2]] & [2, 1] & [2, 1] & 1 & 1\\\hline
s_{2} & (1, 3, 2) & [[1, 2], [3]] & [2, 1] & [2, 1] & 1 & 1\\\hline
s_{1}s_{2}s_{1} & (3, 2, 1) & [[1], [2], [3]] & [1, 1, 1] & [3] & 3 & 3\\\hline

In latex: $$ \begin{array}[|l|c|l|l|l|r|r|] \hline w\in W & w\in S_3 & Q &\text{shape}(Q) &\text{shape}(Q)^t & a\text{ if inv.} &a\\\hline\hline 1 & (1, 2, 3) & [[1, 2, 3]] & [3] & [1, 1, 1] & 0 & 0\\\hline s_{1}s_{2} & (2, 3, 1) & [[1, 2], [3]] & [2, 1] & [2, 1] & & 1\\\hline s_{2}s_{1} & (3, 1, 2) & [[1, 3], [2]] & [2, 1] & [2, 1] & & 1\\\hline s_{1} & (2, 1, 3) & [[1, 3], [2]] & [2, 1] & [2, 1] & 1 & 1\\\hline s_{2} & (1, 3, 2) & [[1, 2], [3]] & [2, 1] & [2, 1] & 1 & 1\\\hline s_{1}s_{2}s_{1} & (3, 2, 1) & [[1], [2], [3]] & [1, 1, 1] & [3] & 3 & 3\\\hline \end{array} $$


Let us do the same also for the $A_3$ case. The code remains, we only change the type in the WeylGroup constructor to A3, the result is in a table...

Later edit: the hline's are not parsed here, so i remove them... (Same computing code, the one print format is changed.) $$ \begin{array}[|l|c|l|l|l|r|r|] \\ w\in W & w\in S_3 & Q &\text{shape}(Q) &\text{shape}(Q)^t & a\text{ if inv.} &a\\\\ 1 & (1, 2, 3, 4) & [[1, 2, 3, 4]] & [4] & [1, 1, 1, 1] & 0 & 0\\ s_{3} & (1, 2, 4, 3) & [[1, 2, 3], [4]] & [3, 1] & [2, 1, 1] & 1 & 1\\ s_{3}s_{2} & (1, 4, 2, 3) & [[1, 2, 4], [3]] & [3, 1] & [2, 1, 1] & & 1\\ s_{3}s_{2}s_{1} & (4, 1, 2, 3) & [[1, 3, 4], [2]] & [3, 1] & [2, 1, 1] & & 1\\ s_{2} & (1, 3, 2, 4) & [[1, 2, 4], [3]] & [3, 1] & [2, 1, 1] & 1 & 1\\ s_{2}s_{3} & (1, 3, 4, 2) & [[1, 2, 3], [4]] & [3, 1] & [2, 1, 1] & & 1\\ s_{2}s_{3}s_{2} & (1, 4, 3, 2) & [[1, 2], [3], [4]] & [2, 1, 1] & [3, 1] & 3 & 3\\ s_{2}s_{3}s_{2}s_{1} & (4, 1, 3, 2) & [[1, 3], [2], [4]] & [2, 1, 1] & [3, 1] & & 3\\ s_{2}s_{1} & (3, 1, 2, 4) & [[1, 3, 4], [2]] & [3, 1] & [2, 1, 1] & & 1\\ s_{2}s_{3}s_{1} & (3, 1, 4, 2) & [[1, 3], [2, 4]] & [2, 2] & [2, 2] & & 2\\ s_{2}s_{3}s_{1}s_{2} & (3, 4, 1, 2) & [[1, 2], [3, 4]] & [2, 2] & [2, 2] & 2 & 2\\ s_{2}s_{3}s_{1}s_{2}s_{1} & (4, 3, 1, 2) & [[1, 4], [2], [3]] & [2, 1, 1] & [3, 1] & & 3\\ s_{1} & (2, 1, 3, 4) & [[1, 3, 4], [2]] & [3, 1] & [2, 1, 1] & 1 & 1\\ s_{3}s_{1} & (2, 1, 4, 3) & [[1, 3], [2, 4]] & [2, 2] & [2, 2] & 2 & 2\\ s_{3}s_{1}s_{2} & (2, 4, 1, 3) & [[1, 2], [3, 4]] & [2, 2] & [2, 2] & & 2\\ s_{3}s_{1}s_{2}s_{1} & (4, 2, 1, 3) & [[1, 4], [2], [3]] & [2, 1, 1] & [3, 1] & & 3\\ s_{1}s_{2} & (2, 3, 1, 4) & [[1, 2, 4], [3]] & [3, 1] & [2, 1, 1] & & 1\\ s_{1}s_{2}s_{3} & (2, 3, 4, 1) & [[1, 2, 3], [4]] & [3, 1] & [2, 1, 1] & & 1\\ s_{1}s_{2}s_{3}s_{2} & (2, 4, 3, 1) & [[1, 2], [3], [4]] & [2, 1, 1] & [3, 1] & & 3\\ s_{1}s_{2}s_{3}s_{2}s_{1} & (4, 2, 3, 1) & [[1, 3], [2], [4]] & [2, 1, 1] & [3, 1] & 3 & 3\\ s_{1}s_{2}s_{1} & (3, 2, 1, 4) & [[1, 4], [2], [3]] & [2, 1, 1] & [3, 1] & 3 & 3\\ s_{1}s_{2}s_{3}s_{1} & (3, 2, 4, 1) & [[1, 3], [2], [4]] & [2, 1, 1] & [3, 1] & & 3\\ s_{1}s_{2}s_{3}s_{1}s_{2} & (3, 4, 2, 1) & [[1, 2], [3], [4]] & [2, 1, 1] & [3, 1] & & 3\\ s_{1}s_{2}s_{3}s_{1}s_{2}s_{1} & (4, 3, 2, 1) & [[1], [2], [3], [4]] & [1, 1, 1, 1] & [4] & 6 & 6\\ \end{array} $$

2020-08-10 10:09:34 -0500 commented question Breaking code into multiple files on Windows

Try to make testa live somewhere where the PYTHONPATH (or sage) finds it. Then check this in the sage ipyton console.

2020-08-10 10:06:07 -0500 commented question not able to execute ./sage

What is ./python3.7 above? (So line 1 from which file?)

Note: A longer time i also had problems with ubuntu+sage, there was no chance to use tbz's, it was even better to use older version from the unmaintained ppa mentioned in

https://launchpad.net/~aims/+archive/...

As this link says, sagemath should be now in debian. My solution was to completely switch to an other distribution. Best for this purpose are the arch based linux distributions. Manjaro did 2y a very good job for me after the first move from ubuntu (and ubuntu based distros), now i am on an arcolinux box, since i could get an arch-like system without any troubles on an older laptop. Consider switching to something else if ubuntu denies access to sage. (And if using sage from debian still makes problems.)

2020-08-10 09:38:58 -0500 answered a question How to modify code to find (calculate) exact generator of curve?

This could not be a comment, so it is posted as an answer.

In such a case it is best to also explain mathematically what is expected and why. So let us digest together.

The code defines a curve $E$ with equation $y^2=x^3+ax+b$ defined over the field with $p$ elements $F$, where

  • $p$ is the prime 2**224 * (2**32 - 1) + 2**192 + 2**96 - 1

  • $a$ is 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC and

  • $b$ is 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B.

The code also gives the order $N$ of $E(F)$.

It is $N=$0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551 .

The curve also comes with a generator, that i will denote by $G$. The $N=$ord below is maybe a prime, at any rate ord * G is E(0). So i would expect that $(E(F),+)$ is isomorphic with the simpler group $(\Bbb Z/N,+)$, a map in one direction being simple, $k\to k*G$.

The following code initializes the data in the above notations in a manner that i understand.

p = 2^224 * (2^32 - 1) + 2^192 + 2^96 - 1
a = ZZ(0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC)
b = ZZ(0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B)

F = GF(p)
E = EllipticCurve(F, [a, b])

ord = ZZ(0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551)

G = E.point( ( ZZ( 0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296 ),
               ZZ( 0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5 ) )
R = Zmod(ord)

Now the framework of the OP becomes even harder to understand (and thus also understanding where is the question), since there are some undefined points like Point1 and Point and some expressions that do not make sense like Point1-1 and Point-3. (Furthermore it is a bad idea to try to reproduce an error using sample code involving a randomizer.)

Note: If we have a point like G on the curve E, then in order to take some multiple of it, say k=2020 times, is is enough to compute k*G. It is no need for taking E( k*G ) to make the code even less readable.

The OP introduces now several (random) integers $k$, and the corresponding points $kG$. Unfortunately these integers have complicated variable names, i will use mine. (Just place yourself in an other place to see how complicated it is to use unexplained variable notations to figure out a simple point...)

# we use now a fixed private key, k0, instead of the privkey. 
k0 = 2020
Q0 = k0 * G

# i have no idea what is a malicious generator, so i will use some special k, k1, instead of kprime...
k1 = R(1234567890)
k2 = 1/k1
Q02 = ZZ(k2) * Q    # so it is k2 * Q = k2 * k0 * G

Now where is the problem?

Please define all variables and try to explain in both mathematical and programatical worlds the issue. (Since the error can be in both of them.)


A final note: Asking a question is both work and effective communication. It is work, since the question should come maximally digested. (For instance, just try to reproduce the situation with small values for $p,a,b,N$. If the problem remains, then post it for these values. Then one can also mention the real framework where the problems shows, but not just copy+paste code from a file written for other purposes.) Always consider that the answer will be longer, and try to already cover with the question a fair share of the effort. The question is always a plus for the community, so write it so that it really lasts longer. This applies also in the case of the other post:

https://math.stackexchange.com/questi...

2020-08-07 18:47:14 -0500 received badge  Good Answer (source)
2020-08-06 04:08:36 -0500 answered a question Built-in tools for fast extraction of tuples of a given grade with respect to grading on [1, 2, ..., n]

For decent values of $n$ one can try the following:

N = 6
S = [1..N]
grading = {1: 1, 2:1, 3: 1, 4: 2, 5: 2, 6: 3}

# Question 0
S2 = Combinations(S,2) 
S2_list = S2.list()
# Alternatively:
S2_list = [(j, k) for j in [1..N] for k in [j+1..N]]

# Question 1
g0 = 4
S2_list_in_deg_g0 = [(j, k) for j in [1..N] for k in [j+1..N] if grading[j] + grading[k] == g0]

# Question 2 :: same game
S3_list_in_deg_g0 = \
    [(j, k, n) for j in [1..N] for k in [j+1..N] for n in [k+1..N] 
     if grading[j] + grading[k] + grading[n] == g0]

S3_list_in_deg_g0_starting_with_one = \
    [(1, k, n) for k in [2..N] for n in [k+1..N] 
     if 1 + grading[k] + grading[n] == g0]

This is slow, since the python loops are slow, but should work good enough for values of $N$ up to $10000$ say. But i wonder if this lists are really needed as lists, to be stored on the HD as such. Instead, if the lists are an intermediate step, iterables may be better. (But python loops are still to slow.) To build the last as an iterable...

S3_iterable_in_deg_g0_starting_with_one = \
    ((1, k, n) for k in [2..N] for n in [k+1..N] 
     if 1 + grading[k] + grading[n] == g0)

For instance, consuming the iterable:

sage: S3_iterable_in_deg_g0_starting_with_one = \ 
....:     ((1, k, n) for k in [2..N] for n in [k+1..N]  
....:      if 1 + grading[k] + grading[n] == g0) 
....:                                                                                                                                                                           
sage: S3_iterable_in_deg_g0_starting_with_one                                                                                                                                   
<generator object <genexpr> at 0x7f5f920eba50>
sage: for triple in S3_iterable_in_deg_g0_starting_with_one: 
....:     print(triple) 
....:                                                                                                                                                                           
(1, 2, 4)
(1, 2, 5)
(1, 3, 4)
(1, 3, 5)

The above solutions are using list comprehension. If the above is slow for the needed purpose, than to improve consider the following ideas:

  • I suppose that $N$ may be bigger $10^6$, but the "grading(s)" have a small range. In our case, the values of the gradings / weights dictionary, taken as a set, is {1,2,3}. Suppose this list is relatively small. (Less than $10^5$.) Then build all tuples of two weights which sum up to g0. Then define the iterable by passing through the weights first.

For instance:

weights = list(set(grading.values()))
weights2 = [(u, v) for u in weights for v in weights if u <= v if u + v == g0]

S2_iterable_in_deg_g0 = \
        ((j, k) for (u, v) in weights2 for j in [1..N-1] for k in [j+1..N] 
         if grading[j] == u and grading[k] == v)

# consume it via...
for tup in S2_iterable_in_deg_g0:
    print(tup)

(The above can be done better...)

  • Use numpy for vectorialization.
2020-08-05 17:42:18 -0500 received badge  Nice Answer (source)
2020-08-05 17:39:56 -0500 received badge  Nice Answer (source)
2020-08-05 17:37:07 -0500 received badge  Nice Answer (source)
2020-08-05 14:49:43 -0500 commented question Configuring an arara rule of sagetex on Windows 10

Yes, i understand, the problem is that the error may highly depend on a given installation and configuration of many pieces of stuff. So we possibly have no chance to detect the error, in such a situation it is best to try yourself to isolate as good as possible the error. Just cut the document block into pieces till the error is eliminated. Then give us that line producing the error.

2020-08-05 13:04:23 -0500 answered a question How can I find the elements in a factor ring?

Here is a possibility...

sage: K.<a> = QuadraticField(2)
sage: OK = K.OK()

sage: OK.gens()                                                                                                                             
(1, a)    sage: J = OK.ideal(3)

sage: Q = OK.quotient(J, names='abar')
sage: Q
Quotient of Maximal Order in Number Field in a with defining polynomial x^2 - 2 with a = 1.414213562373095? by the ideal (3)
sage: Q.is_field()
True
sage: Q.is_prime_field()
False
sage: Q.inject_variables()
Defining abar0, abar1
sage: abar0                                                                                                                                 
1
sage: abar1                                                                                                                                 
a

But do not expect too much functionality from this construction. Instead, why not construct "with bare hands" the ring last listed in the following chain of isomorphisms. (We know that $\mathcal O_K$ is generated by $1$ and $a=(x\text{ mod }(3))$.) $$ \mathcal O_K/(3) =(\Bbb Z[x]/(x^2-2))/3 =\Bbb Z[x]/(x^2-2,\ 3) =(\Bbb Z[x]/3)/(x^2-2) =\Bbb F_3[x]/(x^2-2) \ . $$ Which is:

R.<x> = PolynomialRing(GF(3))                                                                                                         
F.<a> = GF(9, modulus=x^2-2)

Of course, knowing the purpose for the needed code snippet may change the situation.

2020-08-05 12:41:51 -0500 answered a question Sage fails to recognize `1 + (1/2 + i*sqrt(3)/2)^3` is zero

The other two answers are already good and compact, they gave examples, and showed already how to proceed, here is only the explanation for the "poor work" done by the function simplify. Let us define the expression to be simplified to have a handy nickname.

sage: a = 1 + ( 1/2 + i*sqrt(3)/2 )^3                                                                                                       
sage: a.simplify()                                                                                                                          
(1/2*I*sqrt(3) + 1/2)^3 + 1
sage: a.simplify?

So asking for a simplification did not simplify (in the sense of a human). So the last line shows what is doing this method:

sage: a.simplify?                                                                                                                           
Docstring:     
   Return a simplified version of this symbolic expression.

   Note:

     Currently, this just sends the expression to Maxima and converts
     it back to Sage.

   See also:

     "simplify_full()", "simplify_trig()", "simplify_rational()",
     "simplify_rectform()" "simplify_factorial()", "simplify_log()",
     "simplify_real()", "simplify_hypergeometric()",
     "canonicalize_radical()"

and so on. So we obtain a "maxima simplification"". And maxima in known for not trying to touch too much expressions. So the prints just submit this string version of the poorly simplified a. The "See also" part (of the doc string of the simplify function/method) above may be an answer to the question. In such cases, the human part is responsible for the "way to handle expressions". For instance:

If we explicitly expand, we get the result.

sage: a.expand()
0

If we know it should be zero, and are irritated for a second, we can ask for this information explicitly:

sage: a == 0    # this is just an "equation", we have to explicitly bool-evaluate it...                                                     
(1/2*I*sqrt(3) + 1/2)^3 + 1 == 0
sage: bool(_)                                                                                                                               
True

We may try some more simplify methods from the above list...

sage: a.simplify()                                                                                                                          
(1/2*I*sqrt(3) + 1/2)^3 + 1
sage: a.simplify_factorial()                                                                                                                
(1/2*I*sqrt(3) + 1/2)^3 + 1
sage: a.simplify_full()                                                                                                                     
0
sage: a.simplify_rational()                                                                                                                 
0
sage: a.simplify_trig()                                                                                                                     
0
sage: a.canonicalize_radical()                                                                                                              
0

Some of the applied methods make no sense (the factorial and the trig lines), but...

2020-08-05 12:24:28 -0500 commented question Test for a valid entry in a matrix

Again we do not have a code that illustrates the situation. This doesn't matter here maybe, since the answer to the question that can be extracted from the sentence "But what I want to know is that is there a more compact way to obtain the same result." is simply: "Yes". First of all, define a matrix as a matrix, respecting both mathematics and sage. The above code constructs a matrix as a list of lists. This is not a matrix, just type type(M) to get <class 'list'>. Instead...

sage: matrix(QQ, M)
[1 2 3 4]
[2 3 0 1]
[5 4 1 3]

is a true matrix. We also have aids to get good pivots, for instance:

sage: A = matrix(QQ, M)
sage: A.pivots()
(0, 1, 2)
sage: A.pivot_rows()
(0, 1, 2)

Try A.pivots? to see the first drops of information on the method.

2020-08-05 12:09:30 -0500 answered a question How to find the generator of the points on the quartic curve?

To use the sage libraries, we bring the quartic into the Weierstraß form.

First of all, we need a rational point at least on the curve. (I suppose we are working over $\Bbb Q$.) Let us search for a "simple integer" that makes the R.H.S. of the given equation, here using variables $\xi,v$ $$ E(\xi,v)\ :\ y^2 = -2500\xi^4 + 451976\xi^2 - 2500 $$

sage: [xi for xi in [0..200] if (-2500*xi^4 + 451976*xi^2 - 2500).is_square()]                                                                  
[5]

OK, we are lucky, and take the $5$, then slightly change the equation for $(E)$ using the substitution $\xi=u+5$, $u=\xi-5$, so that $u=0$ is leading to a point $(0,3120)=(0,q)$ on the transformed curve:

$$ E(u,v)\ :\ v^2 = -2500u^4 + 50000u^3 + 76976u^2 - 3269760u + \underbrace{9734400}_{q^2}\ . $$ Code finding this equation:

sage: var('u'); 
sage: def f(xi):
....:     return  -2500*xi^4 + 451976*xi^2 - 2500 
....:        

sage: f(u+5).factor()                                                                                                                       
-4*(25*u^2 + 588*u + 2340)*(25*u^2 - 88*u - 1040)
sage: f(u+5).expand()                                                                                                                       
-2500*u^4 - 50000*u^3 + 76976*u^2 + 3269760*u + 9734400

sage: sqrt(9734400)
3120

Now we proceed as in [Ian Conell, Elliptic Curves Hanbook, page 105, Quartic to Weierstrass] . (Wonderful exposition.)

Consider the substitutions that apply in the general situation of a quartic with a rational point (without loss of generality moved in the position $(0,q)$), given by $v^2=au^4 + bu^3 + cu^2 + du+q^2$: $$ x = ( Q(v+q)+du )/u^2\ , $$ $$ y = ( Q^2(v+q) + Q(cu^2+du) - d^2u^2/Q)/u^3\ . $$

See also

https://ask.sagemath.org/question/36637/change-of-variable-from-hyperellictic-curve-to-weierstrass-form/

https://ask.sagemath.org/question/37478/transform-quartic-to-weierstrass/

for other examples.

Then the following code finds the cubic:

var( 'u,v' );

a, b, c, d, q = -2500, -50000, 76976, 3269760, 3120
Q = 2*q

def f(u):
    return a*u^4 + b*u^3 + c*u^2 + d*u + q^2

x = ( Q*(v+q) + d*u ) / u^2
y = ( Q^3*(v+q) + Q^2*( d*u + c*u^2 ) - d^2*u^2 ) / Q / u^3

# inverse transformation:
# u = ( Q*(x+c) - d^2/Q ) / y
# v = -q + u*(u*x-d)/Q

# one can easily define rational functions (u,v) -> (x,y) and (x,y) -> (u,v)
# to be used in the concrete situation

a1 = d/q
a2 = c - (d/Q)^2
a3 = b*Q
a4 = -a*Q^2
a6 = a2*a4

( ( y^2 + a1*x*y + a3*y ) - ( x^3 + a2*x^2 + a4*x + a6 ) ) . factor()

The above gives:

80990208000
    *(2500*u^4 + 50000*u^3 - 76976*u^2 + v^2 - 3269760*u - 9734400)
    *(95*u^2 - 1572*u - 3*v - 9360)/u^6

(The result was manually broken to fit somehow in shorter lines.) One factor corresponds to the equation of $E(u,v)$ after using the birational transformations mentioned in the code. Now we consider the corresponding curve, and ask for rank, and generator(s).

E = EllipticCurve(QQ, [a1, a2, a3, a4, a6])
print(f"E is the elliptic curve:\n{E}")
print(f"E has rank {E.rank()}")
P = E.gens()[0]
print(f"Generator: P = {P.xy()}")

We obtain (result manually broken again):

E is the elliptic curve:
Elliptic Curve defined by 
    y^2 + 1048*x*y - 312000000*y = x^3 - 197600*x^2 + 97344000000*x - 19235174400000000
over Rational Field
E has rank 1
Generator: P = (4798560, 8222323200)

It remains to bring this generator back in the $(u,v)$ then $(\xi,v)$ word.

x, y = P.xy()
u = ( Q*(x+c) - d^2/Q ) / y
v = -q + u*(u*x-d)/Q
xi = u + 5
print(f"(xi, v) = ({xi}, {v})")

We get:

(xi, v) = (1537/181, 145001328/32761)

Well, this is an "ugly" point... To get simpler points, we many try...

points = []
for n in [-5..-1] + [1..5]:
    for T in E.torsion_points():
        R = n*P + T
        x, y = R.xy()
        u = ( Q*(x+c) - d^2/Q ) / y
        v = -q + u*(u*x-d)/Q
        xi = u + 5
        points.append((xi, v))

points.sort(key=lambda point: len(str(point)))
for point in points[:8]:
    print(point)

But in the list there are no really simpler points. Here is the list, reminding us that the given equation was reciprocal on the R.H.S. :

(1537/181, 145001328/32761)
(-1537/181, 145001328/32761)
(1537/181, -145001328/32761)
(181/1537, 145001328/2362369)
(-1537/181, -145001328/32761)
(-181/1537, 145001328/2362369)
(181/1537, -145001328/2362369)
(3281/9125, 787407504/3330625)

Let us check that the first point is on the given curve:

def p(xi, v):
    return v^2 - ( -2500*xi^4 + 451976*xi^2 - 2500 )
print(p(1537/181, 145001328/32761))

Yes, we obtain a clean zero.

2020-08-04 03:23:33 -0500 commented question how to delete all programs, inputs and output in the sage console ?

Just start a new console and a new sage process inside it.

2020-08-04 03:21:01 -0500 commented question Configuring an arara rule of sagetex on Windows 10

A minimal text in the document block, that still produces the error, may better isolate its reason and lead to the (needed escape sequence for the) solution...

2020-08-04 03:14:55 -0500 answered a question Concatenation of symbolic vectors.

It is hard to understand what and why should be done, but maybe the following will do the job. The presented solution is just blind plain work to avoid follow up questions. (It is hard to understand why vectors should be used, lists are better suited. And lists can be easily concatenated. But ok... )

x1 = var('x1', latex_name='x_1')                                                                                                                        
x2 = var('x2', latex_name='x_2')                                                                                                                        
x3 = var('x3', latex_name='x_3')                                                                                                                        
x4 = var('x4', latex_name='x_4')                                                                                                                        

e1 = var('e1', latex_name=r'\epsilon_1')                                                                                                                
e2 = var('e2', latex_name=r'\epsilon_2')                                                                                                                
e3 = var('e3', latex_name=r'\epsilon_3')                                                                                                                

b  = var('b' , latex_name='b')                                                                                                                          

v = [x1, x2, x3, x4, e1, e2, e3, b]

Then in the sage interpreter:

sage: vector(v)                                                                                                                                               
(x1, x2, x3, x4, e1, e2, e3, b)
sage: show(vector(v))                                                                                                                                         
\newcommand{\Bold}[1]{\mathbf{#1}}\left({x_1},\,{x_2},\,{x_3},\,{x_4},\,{\epsilon_1},\,{\epsilon_2},\,{\epsilon_3},\,{b}\right)
sage: latex(v)                                                                                                                                                
\left[{x_1}, {x_2}, {x_3}, {x_4}, {\epsilon_1}, {\epsilon_2}, {\epsilon_3}, {b}\right]
2020-08-03 11:14:47 -0500 commented question Discrete log in quotient rings of univariate polynomial rings

In general, a quotient of the shape $\Bbb F_p[x]/(f)$ is a field for a fixed, irreducible polynomial $f$. Let $n$ be its degree. Up to isomorphism, there is "exactly one field" with $q=p^n$ elements. We may denote it by $\Bbb F_q$. (But it is practically in sage also constructed in the same manner for an other polynomial. Well, i need a handy notation. In fact, sage can take $f$ as modulus directly.) So $\Bbb F_p/(f)\cong \Bbb F_q$. The structure of the multiplicative group $(\Bbb F_q^\times,\cdot)$ of invertible (i.e. non-zero) elements in this field is known. It is a group of order $(q-1)$ with one generator. We can ask sage to give us a generator. Now, in practice, we need to know something explicitly, in order to solve something explicitly, please provide explicit data.

2020-08-03 11:07:05 -0500 commented question How to transform coordinate of point on elliptic curve from curve x^3+5 to x^3+2 ?

Please give references to the elliptic curve, and show the own attempts. Explicitly, please provide code that initializes the elliptic curve (including the base field $\Bbb F_q$ for some prime power $q$. Also give $q$.) So as it is, the question makes no sense. Please edit the question to have a well defined question with a fair share of the effort.

2020-08-03 10:57:58 -0500 commented question Count points on elliptic curve secp256k1 with another p

I edited the lines in the question, marking the many letters that may be part of a pseudo-code as code, but we still have no well defined question. To have a well defined question, we need the "other" p and the parameters for the "new" curve. For small values of p, sage can compute via E.order() the number of $\Bbb F_p$-rational points, e.g.

sage: E = EllipticCurve(GF(7), [3,4])                                                                                         
sage: E.order()                                                                                                               
10

but for greater values, we have to invest mathematical effort to find the "order". (Of $E(\Bbb F_p)$.) Please fill in all needed defining data. And best give references / links.

2020-08-03 09:08:05 -0500 edited question Count points on elliptic curve secp256k1 with another p

Example:

secp192k1': 

_ECData( p=2192 - 232 - 212 - 28 - 27 - 26 - 2**3 - 1, a=0, b=3, 
Gx=0xDB4FF10EC057E9AE26B07D0280B7F4341DA5D1B1EAE06C7D, 
Gy=0x9B2F2F6D9C5628A7844163D015BE86344082AA88D95E2F9D,
n=0xFFFFFFFFFFFFFFFFFFFFFFFE26F2FC170F69466A74DEFD8D

I have another curve (with another p(!), similar base point and equation ) parameters.

I need to calculate n

How can I do it with code in sage, python or another software please?

Br

2020-06-30 12:18:51 -0500 answered a question Solving a polynomial system in a quotient ring

Here is a possibility to work.

Let $A$ be a ring such that $2$ is invertible, for example $\Bbb Z/3$ or $\Bbb Z/9$. We denote by $\frac 12$ its inverse. Assume $2$ is not a square in $A$. (This is the case in the above examples.)

Consider $A[a]$ to be the ring $A[Y]/(Y^2-2)$, where $A[Y]$ is the polynomial ring in $Y$ over $A$. (And $a$ is $Y$ modulo the ideal generated by $(Y^2-2)$. So formally, $a=\sqrt2$.

Now observe that the equation satisfied by the $x$ element in the OP, $(x+a)^2=2(x+a)$, can be written as $$(x+a)(x+a-2)=0\ .$$ The two factors are relatively prime, in fact $$\frac 12(x+a)-\frac 12(x+a-2) = 1\ .$$ This means that the ring $$ R=A[a][X]\ /\ (\ (X+a)(X+a-2)\ ) $$ is isomorphic to two copies of $A[a]$ via the map $$ R\to A[a]\times A[a]\ ,\ f(X)\to(f(-a), f(2-a))\ . $$ The inverse map takes $(s,t)\in A[a]\times A[a]$ and maps it into $\frac 12t(X+a)-\frac 12s(X+a-2)$.

Now we have to solve $Z^2=1$ in the ring $A[a]\times A[a]$. This can be done also manually. An element of the shape $Z=u+va\in A[a]$, $u,v\in A$ satisfies $Z^2 = 1$ iff $(u^2+2v^2)+2auv=1$. In case $A$ has zero divisors we have to take care of $uv=0$ somehow. The possible values for $u,v$ that may lead to a solution satisfy at any rate $u^3=u$ and $2v^3=v$. Together with $Z$, also its "conjugate" $\bar Z=u-va$ is also a solution, and the "norm" $N(Z)=Z\bar Z=(u+va)(u-va)=u^2-2v^2$ is $1$. So it is a good idea to search for solutions of this "Pell equation" over $A$.

Let us now write some lines of code for the given case.

The brute force search is:

r = Zmod(9)
R.<a,x> = PolynomialRing(r, order='lex')
J = R.ideal( [a^2-2, (x+a)^2-2*(x+a)] )
S = R.quotient(J)

for [s, t, u] in cartesian_product([r, r, r]):
    Z = S(s + t*a + u*x)
    if Z^2 == S(1):
        print(f"Z = {s} + {t} a + {u} x")

Results:

Z = 1 + 0 a + 0 x
Z = 1 + 8 a + 8 x
Z = 8 + 0 a + 0 x
Z = 8 + 1 a + 1 x

This fits with the situation of finding all points $Z=(Z_1,Z_2)$ over the ring $R=A[a]=\Bbb Z/9[a]=\Bbb Z/9[\sqrt 2]$ with $Z^2=(1,1)=1_R$.

sage: r = Integers(9)                                                                                                         
sage: R.<Y> = r[]                                                                                                             
sage: Q.<a> = R.quotient(Y^2-2)                                                                                               
sage: a^2                                                                                                                     
2
sage: for r1, r2 in cartesian_product([r, r]): 
....:     Z1 = r1 + r2*a 
....:     if Z1^2 == Q(1): 
....:         print(Z1) 
....:                                                                                                                         
1
8

These are the only Hensel lifts of the corresponding units over $\Bbb Z/3$:

sage: U.<A> = PolynomialRing(GF(3))                                                                                           
sage: F.<a> = GF(3^2, modulus = A^2-2)                                                                                        
sage: a^2                                                                                                                     
2
sage: [ f for f in F if f^2 == F(1) ]                                                                                         
[2, 1]
sage: # of course, this is a field...
2020-06-30 09:43:53 -0500 received badge  Nice Answer (source)
2020-06-29 04:19:12 -0500 commented question Solve command doesnt give proper results

It is hard to understand the sense of the equations, so as they are written. First of all, do we need that part - tan(a)+tan(a)+tan(b)-tan(b) in eq3, and the corresponding part in eq4?! If not, we also do not need b,c in the story. Substitute $t$ for $\tan a$, and ask for the solution of the corresponding system in m, x1, x2, t. (Assuming that sage solves every fancy system of equation is not a good idea. Sometimes it is best to do the best job on the mathematical part, then offer sage a clean setting.)

2020-06-29 03:57:38 -0500 answered a question Find elements of left coset ZZ_6/{0,3}

Note that the sage instances corresponding to the ring $(\Bbb Z/6,+,\cdot)$, and to the cyclic abelian group $(C_6,+)$ differ, as it also happens in the mathematical world. The quotient in the category of rings is built w.r.t. an ideal, in our case the ideal is generated by $3\in \Bbb Z/6$. In the category of abelian groups we mod out a subgroup, in our case the subgroup is generated by $3$. Let us construct the quotient in both cases.

In the category of rings, we introduce the ring $R$ by either of...

sage: Integers(6)                                                                                                                                             
Ring of integers modulo 6
sage: Zmod(6)                                                                                                                                                 
Ring of integers modulo 6
sage: IntegerModRing(6)                                                                                                                                       
Ring of integers modulo 6

then consider its ideal $J=(3)$, and the quotient:

sage: R = Zmod(6)                                                                                                                                             
sage: R                                                                                                                                                       
Ring of integers modulo 6
sage: J = R.ideal(3)                                                                                                                                          
sage: J                                                                                                                                                       
Principal ideal (3) of Ring of integers modulo 6
sage: list(R)                                                                                                                                                 
[0, 1, 2, 3, 4, 5]
sage: Q = R.quotient(J)                                                                                                                                       
sage: Q                                                                                                                                                       
Ring of integers modulo 3
sage: for k in R: 
....:     print(f"{k} modulo J is {Q(k)}") 
....:                                                                                                                                                         
0 modulo J is 0
1 modulo J is 1
2 modulo J is 2
3 modulo J is 0
4 modulo J is 1
5 modulo J is 2
sage:

In the category of abelian groups (and/or in the category of groups) one can construct:

sage: C6.<a> = AbelianGroup(1, [6])                                                                                                                           
sage: C6                                                                                                                                                      
Multiplicative Abelian group isomorphic to C6
sage: # or                                                                                                                                                    
sage: C6 = CyclicPermutationGroup(6)                                                                                                                          
sage: a = C6.gens()[0]                                                                                                                                        
sage: a.order()                                                                                                                                               
6
sage: a                                                                                                                                                       
(1,2,3,4,5,6)

And the quotient is...

sage: H = C6.subgroup([a^3])                                                                                                                                  
sage: Q = C6.quotient(H)                                                                                                                                      
sage: Q                                                                                                                                                       
Permutation Group with generators [(1,2,3)]

Unfortunately, the version using C6.<a> = AbelianGroup(1, [6]) was leading to a sage crash on my machine while trying to build the quotient with respect to the subgroup H constructed mot-a-mot as above. So just use the construction involving a permutation group.

2020-06-26 20:11:55 -0500 answered a question Can you help me write an algorithm that gives me the number of k subsets of a n member set? like {1,2,3}--->two subset---->[{1,2},{1,3},{2,3}]

Yet "an other" possibility, we use the sage specific Combinations. For instance:

sage: S = [1, 2, 3, 5]                                                                                                                                        
sage: Combinations(S, 2)                                                                                                                                      
Combinations of [1, 2, 3, 5] of length 2
sage: for A in Combinations(S, 2): 
....:     print(A) 
....:                                                                                                                                                         
[1, 2]
[1, 3]
[1, 5]
[2, 3]
[2, 5]
[3, 5]
sage:
2020-06-15 10:45:57 -0500 answered a question Exponential for formal group of elliptic curve

This is a later answer, hoping that the quick good answer of FrédéricC will be accepted.

Let us place the above in the context of a sample elliptic curve, my choice is

E = EllipticCurve(QQ, [-1, 0])
FormalGroupOfE = E.formal_group()
f = FormalGroupOfE.log(prec=20)
print(f)

This gives:

t - 2/5*t^5 + 2/3*t^9 - 20/13*t^13 + 70/17*t^17 + O(t^20)

Here, t is a printed variable, that does not exist so far as t, so we introduce it.

sage: t = f.parent().gens()[0]                                                                                                
sage: t                                                                                                                       
t

Now we can associate the reverse object, and check the compositions...

sage: g = f.reverse()                                                                                                         
sage: g                                                                                                                       
t + 2/5*t^5 + 2/15*t^9 + 44/975*t^13 + 422/27625*t^17 + O(t^20)
sage: g(f(t))                                                                                                                 
t + O(t^20)
sage: f(g(t))                                                                                                                 
t + O(t^20)

If $F$ is the "group law" of the formal group,

sage: F = FormalGroupOfE.group_law()                                                                                          
sage: F                                                                                                                       
t1 + t2 + 2*t1^4*t2 + 4*t1^3*t2^2 + 4*t1^2*t2^3 + 2*t1*t2^4 - 2*t1^8*t2
    + 8*t1^6*t2^3 + 16*t1^5*t2^4 + 16*t1^4*t2^5 + 8*t1^3*t2^6 - 2*t1*t2^8
    + O(t1, t2)^10

(code was split manually,) and we have by definition $f(\ F(x,y)\ )=f(x)+f(y)$, so let us check the relation obtained from this one, after applying $g$:

sage: t1, t2 = F.parent().gens()                                                                                              
sage: F(t1, t2) == g( f(t1) + f(t2) )                                                                                         
True