# Computing a formula in SAGE

Fix the positive integer numbers $t_1, t_2, t_3,t_4, t_5.$ We have the following formula:

$$S= \sum_{i, j, h, m, k_1 + k_2+k_3+k_4 = i-t_1, \ell_1+\ell_2 + \ell_3 = j -t_2 + k_4, u_1 + u_2 = h - t_3+k_3+\ell_3 }M_1.M_2.M_3. M_4,$$ where

$$M_1 = \binom{t_5-k_1}{k_1}\binom{t_4-k_2}{k_2}\binom{t_3-k_3}{k_3}\binom{t_2-k_4}{k_4}$$ $$M_2 = \binom{t_5-k_1-\ell_1}{\ell_1}\binom{t_4-k_2-\ell_2}{\ell_2}\binom{t_3-k_3-\ell_3}{\ell_3}$$ $$M_3 = \binom{t_5-k_1-\ell_1-u_1}{u_1}\binom{t_4-k_2-\ell_2-u_2}{u_2};$$ $$M_4=\binom{t_1+t_2+t_3+t_4 +t_5-i - j-h-m}{m - t_4 + k_2+ \ell_2 + u_2}.\lambda_i\lambda_j\lambda_h\lambda_m\lambda_{t_1+t_2 + t_3+t_4+t_5 - i - j-h-m}$$ Here, the binomial factors $\binom{n}{k}$ mod 2 and the value of $S$ mod 2. By convention, $\binom{n}{k} \equiv 0$ (mod 2) if either $k < 0$ or $n < 0$ or $k > n.$

I don't how to construct this formula in SAGE. Can someone show me how to compute it using SAGE?

edit retag close merge delete

1

What are $\lambda$ and what are the bounds for the other variables? If it is an infinite series then you will want to compute a single coefficient first. Also a source would help.

( 2019-08-20 07:37:29 +0200 )edit

Thank you very much! The number $\lambda$ is fixed.

( 2019-08-20 10:25:21 +0200 )edit
1

If $\lambda$ is a number then what do the subscripts mean? Are $i,j,h,m,k_1,k_2,k_3,k_4,\ell_1,\ell_2,\ell_3,u_1,u_2$ nonnegative? Alternatively/additionally, where exactly does this formula come from? (Probably the source will answer my questions.)

( 2019-08-20 11:51:08 +0200 )edit

Yes, the subscripts $i, j, h, m, k_1, k_2, k_3, k_4, \ell_1, \ell_2, \ell_3, u_1, u_2$ are nonnegative. Here $\lambda$ is fixed. I hope that you can help me set up the above formula in Sage. Thank you very much!

( 2019-08-20 12:58:02 +0200 )edit
1

Is $S$ a polynomial of degree 5 in the infinitely many variables $\lambda_n$? Are $k_1\leqslant k_2 \leqslant k_3 \leqslant k_4$ and $\ell_1 \leqslant \ell_2 \leqslant \ell_3$ and $u_1 \leqslant u_2$ or not? (That is, ordered partitions or all partitions?)

( 2019-08-20 13:37:21 +0200 )edit

Sort by ยป oldest newest most voted

This is a polynomial of degree $5$ in the noncommutative variables $\lambda_n$ where the sum of the indices in each monomial is $t_1+t_2+t_3+t_4+t_5$.

It seems Sage doesn't easily generate partitions of $n$ into $k$ nonnegative integers, so we implement this helper function for it (we partition $n+k$ into $k$ positive integers and subtract 1 from each one):

def nonnegative_partitions(n, length):
from itertools import permutations
for part in Partitions(n+length, length=length):
seen = set([])
for shuffled_part in permutations(part):
shuffled_part = tuple(x-1 for x in shuffled_part)
if not shuffled_part in seen:
yield shuffled_part


Here we also take care that $4 = 2+2$ is counted only once. You can implement the formula as:

def S(t):
F2 = GF(2)
Lamb = FreeAlgebra(F2, sum(t)+1, names='l_')
lamb = Lamb.gens()
result = Lamb.zero()
for indices in nonnegative_partitions(sum(t), length=5):
(i,j,h,m,idc) = indices
for k in nonnegative_partitions(i-t[0], length=4):
M1 = F2(binomial(t[4]-k[0], k[0]) * binomial(t[3]-k[1], k[1]) * binomial(t[2]-k[2], k[2]) * binomial(t[1]-k[3], k[3]))
for l in nonnegative_partitions(j-t[1]+k[3], length=3):
M2 = F2(binomial(t[4]-k[0]-l[0], l[0]) * binomial(t[3]-k[1]-l[1],l[1]) * binomial(t[2]-k[2]-l[2],l[2]))
for u in nonnegative_partitions(h-t[2]+k[2]+l[2], length=2):
M3 = F2(binomial(t[4]-k[0]-l[0]-u[0], u[0]) * binomial(t[3]-k[1]-l[1]-u[1],u[1]))
M4 = F2(binomial(sum(t)-sum([i,j,h,m]), m-t[3]+k[1]+l[1]+u[1]))
result += M1*M2*M3*M4*lamb[i]*lamb[j]*lamb[h]*lamb[m]*lamb[idc]
return result


For example,

sage: S((1,2,3,4,5))
l_1*l_2*l_3*l_4*l_5 + l_1*l_2*l_3*l_6*l_3 + l_1*l_2*l_4*l_3*l_5 + l_1*l_2*l_4*l_5*l_3 + l_1*l_2*l_5*l_2*l_5 + l_1*l_2*l_6*l_3^2 + l_1*l_2*l_7*l_2*l_3 + l_1*l_2*l_8*l_1*l_3 + l_1*l_2*l_9*l_0*l_3 + l_1*l_3^3*l_5 + l_1*l_3^2*l_5*l_3 + l_1*l_3*l_5*l_3^2 + l_1*l_3*l_7*l_1*l_3 + l_1*l_4*l_3*l_2*l_5 + l_1*l_4^2*l_1*l_5 + l_1*l_4*l_7*l_0*l_3 + l_1*l_5*l_3^3 + l_1*l_6*l_0*l_3*l_5 + l_1*l_6*l_0*l_5*l_3 + l_1*l_6*l_1*l_2*l_5 + l_1*l_6*l_2*l_3^2 + l_1*l_6*l_5*l_0*l_3 + l_1*l_7*l_1*l_3^2 + l_1*l_8*l_0*l_1*l_5 + l_1*l_10*l_1*l_0*l_3 + l_2*l_1*l_3*l_4*l_5 + l_2*l_1*l_3*l_6*l_3 + l_2*l_1*l_4*l_3*l_5 + l_2*l_1*l_4*l_5*l_3 + l_2*l_1*l_5*l_2*l_5 + l_2*l_1*l_6*l_3^2 + l_2*l_1*l_7*l_2*l_3 + l_2*l_1*l_8*l_1*l_3 + l_2*l_1*l_9*l_0*l_3 + l_2*l_3^2*l_2*l_5 + l_2*l_3*l_4*l_1*l_5 + l_2*l_3*l_7*l_0*l_3 + l_2*l_5*l_0*l_3*l_5 + l_2*l_5*l_0*l_5*l_3 + l_2*l_5*l_1*l_2*l_5 + l_2*l_5*l_2*l_3^2 + l_2*l_5^2*l_0*l_3 + l_2*l_7*l_0*l_1*l_5 + l_2*l_9*l_1*l_0*l_3 + l_3*l_1*l_3^2*l_5 + l_3*l_1*l_3*l_5*l_3 + l_3*l_1*l_5*l_3^2 + l_3*l_1*l_7*l_1*l_3 + l_3*l_2*l_3*l_2*l_5 + l_3*l_2*l_4*l_1*l_5 + l_3*l_2*l_7*l_0*l_3 + l_3^3*l_1*l_5 + l_3^5 + l_3*l_5*l_1*l_3^2 + l_3*l_6*l_0*l_1*l_5 + l_4*l_0*l_3^2*l_5 + l_4*l_0*l_3*l_5*l_3 + l_4*l_0*l_5*l_3^2 + l_4*l_0*l_7*l_1*l_3 + l_4*l_2*l_3*l_1*l_5 + l_4*l_3*l_0*l_3*l_5 + l_4*l_3*l_0*l_5*l_3 + l_4*l_3*l_1*l_2*l_5 + l_4*l_3*l_2*l_3^2 + l_4*l_3*l_5*l_0*l_3 + l_4^2*l_1*l_3^2 + l_4*l_7*l_1*l_0*l_3 + l_5*l_0*l_3*l_2*l_5 + l_5*l_0*l_4*l_1*l_5 + l_5*l_0*l_7*l_0*l_3 + l_5*l_1*l_3^3 + l_5*l_3*l_1*l_3^2 + l_5*l_4*l_3*l_0*l_3 + l_5*l_6*l_1*l_0*l_3 + l_6*l_0*l_3*l_1*l_5 + l_6*l_3*l_0*l_1*l_5 + l_6*l_3^2*l_0*l_3 + l_6*l_5*l_1*l_0*l_3 + l_8*l_0*l_1*l_3^2 + l_8*l_1*l_0*l_1*l_5 + l_8*l_1*l_3*l_0*l_3 + l_9*l_0*l_3*l_0*l_3


When you compute S(t) for several t with different sum(t) then they will belong to different FreeAlgebras (with different number of generators $\lambda_n$), but the names of the generators are "compatible", so adding elements should coerce them into the larger parent FreeAlgebra. Unfortunately this doesn't work (yet), so you have to use a workaround like this:

sage: S_1 = S((1,1,1,3,4)); S_2 = S((1,2,3,4,5)); S_3 = S((1,1,1,6,6))
sage: S_2.parent()
Free Algebra on 16 generators (l_0, l_1, l_2, l_3, l_4, l_5, l_6, l_7, l_8, l_9, l_10, l_11, l_12, l_13, l_14, l_15) over Finite Field of size 2
sage: S_2.parent() == S_3.parent() # the biggest FreeAlgebra that contains all of them
True
sage: S_2.parent()(str(S_1)) + S_2 + S_3
l_1^3*l_3*l_4 + l_1^3*l_4*l_3 + l_1^3*l_5*l_2 + l_1^3*l_6^2 + l_1^3*l_7*l_5 + l_1^3*l_9*l_3 + l_1^2*l_2*l_3^2 + l_1^2*l_2*l_5*l_6 + l_1^2*l_3^2*l_2 + l_1^2*l_3*l_4*l_1 + l_1^2*l_3*l_5^2 + l_1^2*l_3*l_7*l_3 + l_1^2*l_4*l_3*l_6 + l_1^2*l_4^2*l_5 + l_1^2*l_5*l_0*l_3 + l_1^2*l_5*l_1*l_2 + l_1^2*l_5*l_3*l_5 + l_1^2*l_7*l_0*l_1 + l_1^2*l_7*l_3^2 + l_1^2*l_8*l_0*l_5 + l_1^2*l_8*l_2*l_3 + l_1*l_2*l_1*l_3^2 + l_1*l_2*l_1*l_5*l_6 + l_1*l_2*l_3^2*l_6 + l_1*l_2*l_3*l_6*l_3 + l_1*l_2*l_4*l_3*l_5 + l_1*l_2*l_4*l_5*l_3 + l_1*l_2*l_5*l_2*l_5 + l_1*l_2*l_6*l_3^2 + l_1*l_2*l_7*l_0*l_5 + l_1*l_2*l_8*l_1*l_3 + l_1*l_2*l_9*l_0*l_3 + l_1*l_3*l_0*l_3^2 + l_1*l_3*l_0*l_5*l_6 + l_1*l_3*l_2*l_3*l_1 + l_1*l_3*l_2*l_3*l_6 + l_1*l_3*l_2*l_4*l_5 + l_1*l_3^2*l_0*l_3 + l_1*l_3^2*l_1*l_2 + l_1*l_3^3*l_5 + l_1*l_3^2*l_5*l_3 + l_1*l_3*l_5*l_3^2 + l_1*l_3*l_6*l_0*l_5 + l_1*l_3*l_6*l_2*l_3 + l_1*l_4*l_2*l_3*l_5 + l_1*l_4*l_3*l_2*l_5 + l_1*l_4^2*l_1*l_5 + l_1*l_4*l_6*l_1*l_3 + l_1*l_4*l_7*l_0*l_3 + l_1*l_5*l_0*l_3*l_1 + l_1*l_5*l_0*l_3*l_6 + l_1*l_5*l_0*l_4*l_5 + l_1*l_5*l_1*l_3*l_5 + l_1*l_5*l_3*l_0*l_1 + l_1*l_5*l_3^3 + l_1*l_5*l_4*l_0*l_5 + l_1*l_5*l_4*l_2*l_3 + l_1*l_6*l_0*l_5*l_3 + l_1*l_6*l_1*l_2*l_5 + l_1*l_6*l_2*l_3^2 + l_1*l_6*l_4*l_1*l_3 + l_1*l_6*l_5*l_0*l_3 + l_1*l_7*l_1*l_0*l_1 + l_1*l_7*l_1*l_3^2 + l_1*l_8*l_0*l_1*l_5 + l_1*l_9*l_0^2*l_5 + l_1*l_9*l_0*l_2*l_3 + l_1*l_9*l_1^2*l_3 + l_1*l_10*l_0*l_1*l_3 + l_1*l_10*l_1*l_0*l_3 + l_2*l_1^2*l_3^2 + l_2*l_1^2*l_5*l_6 + l_2*l_1*l_3^2*l_6 + l_2*l_1*l_3*l_6*l_3 + l_2*l_1*l_4*l_3*l_5 + l_2*l_1*l_4*l_5*l_3 + l_2*l_1*l_5*l_2*l_5 + l_2*l_1*l_6*l_3^2 + l_2*l_1*l_7*l_0*l_5 + l_2*l_1*l_8*l_1*l_3 + l_2*l_1*l_9*l_0*l_3 + l_2*l_3*l_2*l_3*l_5 + l_2*l_3^2*l_2*l_5 + l_2*l_3*l_4*l_1*l_5 + l_2*l_3*l_6*l_1*l_3 + l_2*l_3*l_7*l_0*l_3 + l_2*l_5*l_0*l_5*l_3 + l_2*l_5*l_1*l_2*l_5 + l_2*l_5*l_2*l_3^2 + l_2*l_5*l_4*l_1*l_3 + l_2*l_5^2*l_0*l_3 + l_2*l_7*l_0*l_1*l_5 + l_2*l_9*l_0*l_1*l_3 + l_2*l_9*l_1*l_0*l_3 + l_3*l_0*l_1*l_3^2 + l_3*l_0*l_1*l_5*l_6 + l_3*l_0*l_3^2*l_6 + l_3*l_0*l_3*l_4*l_5 + l_3*l_0*l_7*l_0*l_5 + l_3*l_0*l_7*l_2*l_3 + l_3*l_1*l_3^2*l_5 + l_3*l_1*l_3*l_5*l_3 + l_3*l_1*l_5*l_3^2 + l_3*l_1*l_7*l_1*l_3 + l_3*l_2*l_1*l_3*l_1 + l_3*l_2*l_1*l_3*l_6 + l_3*l_2*l_1*l_4*l_5 + l_3*l_2^2*l_3*l_5 + l_3*l_2*l_3*l_2*l_5 + l_3*l_2*l_4*l_1*l_5 + l_3*l_2*l_5*l_0*l_5 + l_3*l_2*l_5*l_2*l_3 + l_3*l_2*l_6*l_1*l_3 + l_3*l_2*l_7*l_0*l_3 + l_3^2*l_0*l_3*l_1 + l_3^2*l_0*l_3*l_6 + l_3^2*l_0*l_4*l_5 + l_3^3*l_0*l_1 + l_3^3*l_1*l_5 + l_3^5 + l_3^2*l_4*l_0*l_5 + l_3^2*l_4*l_2*l_3 + l_3^2*l_5*l_1*l_3 + l_3*l_4*l_3*l_0*l_5 + l_3*l_4*l_3*l_2*l_3 + l_3*l_5*l_1*l_3^2 + l_3*l_5*l_3*l_1*l_3 + l_3*l_6*l_0*l_1*l_5 + l_3*l_7*l_0^2*l_5 + l_3*l_7*l_0*l_2*l_3 + l_3*l_7*l_1^2*l_3 + l_4*l_0*l_3^2*l_5 + l_4*l_0*l_3*l_5*l_3 + l_4*l_0*l_5*l_3^2 + l_4*l_0*l_7*l_1*l_3 + l_4*l_2*l_1*l_3*l_5 + l_4*l_2*l_3*l_1*l_5 + l_4*l_2*l_5*l_1*l_3 + l_4*l_3*l_0*l_5*l_3 + l_4*l_3*l_1*l_2*l_5 + l_4*l_3*l_2*l_3^2 + l_4*l_3*l_4*l_1*l_3 + l_4*l_3*l_5*l_0*l_3 + l_4^2*l_1*l_3^2 + l_4^2*l_3*l_1*l_3 + l_4*l_7*l_0*l_1*l_3 + l_4*l_7*l_1*l_0*l_3 + l_5*l_0*l_1*l_3*l_1 + l_5*l_0*l_1*l_3*l_6 + l_5*l_0*l_1*l_4*l_5 + l_5*l_0*l_2*l_3*l_5 + l_5*l_0*l_3*l_2*l_5 + l_5*l_0*l_4*l_1*l_5 + l_5*l_0*l_5*l_0*l_5 + l_5*l_0*l_5*l_2*l_3 + l_5*l_0*l_6*l_1*l_3 + l_5*l_0*l_7*l_0*l_3 + l_5*l_1^2*l_3*l_5 + l_5*l_1*l_3^3 + l_5*l_1*l_5*l_1*l_3 + l_5*l_3*l_1*l_3^2 + l_5*l_3*l_2*l_0*l_5 + l_5*l_3*l_2^2*l_3 + l_5*l_4*l_2*l_1*l_3 + l_5*l_4*l_3*l_0*l_3 + l_5^2*l_0^2*l_5 + l_5^2*l_0*l_2*l_3 + l_5^2*l_1^2*l_3 + l_5*l_6*l_0*l_1*l_3 + l_5*l_6*l_1*l_0*l_3 + l_6*l_0*l_1*l_3*l_5 + l_6*l_0*l_3*l_1*l_5 + l_6*l_0*l_5*l_1*l_3 + l_6*l_3*l_0*l_1*l_5 + l_6*l_3*l_2*l_1*l_3 + l_6*l_3^2*l_0*l_3 + l_6*l_5*l_0*l_1*l_3 + l_6*l_5*l_1*l_0*l_3 + l_7*l_0^2*l_3*l_5 + l_7*l_0*l_4*l_1*l_3 + l_7*l_1*l_2*l_0*l_5 + l_7*l_1*l_2^2*l_3 + l_7*l_2^2*l_1*l_3 + l_8*l_0*l_1*l_3^2 + l_8*l_1*l_0*l_1*l_5 + l_8*l_1*l_2*l_1*l_3 + l_8*l_1*l_3*l_0*l_3 + l_9*l_0*l_2*l_1*l_3 + l_9*l_0*l_3*l_0*l_3 + l_11*l_0^2*l_1*l_3

more

I have copied your code into Sage online https://sagecell.sagemath.org/. However, it reports an error File "<ipython-input-1-70610415ffb6>", line 26 sage: S((Integer(1),Integer(2),Integer(3),Integer(4),Integer(5))) ^ SyntaxError: invalid syntax</ipython-input-1-70610415ffb6>

( 2019-08-20 16:55:50 +0200 )edit
( 2019-08-20 17:08:12 +0200 )edit

Thank you very much!

( 2019-08-20 17:31:47 +0200 )edit

In the online version of Sagemath https://sagecell.sagemath.org/, for S((1,2,3,4,5)), it is not found the result.

( 2019-08-21 01:43:41 +0200 )edit

Moreover, the monomial $\lambda_a\lambda_b\lambda_c\lambda_d\lambda_e$ is not ordere partitions. More presely, the subscripts $a, b, c, d, e$ are not necessary to order partition. For example, $S = \lambda_1\lambda_3\lambda_2^2\lambda_4\lambda_5 + \lambda_3\lambda_2^2\lambda_1\lambda_4\lambda_5 + \lambda_1\lambda_2^2\lambda_3\lambda_4\lambda_5.$

( 2019-08-21 03:06:45 +0200 )edit

Yes, S((1,2,3,4,5)) takes a while, so you need to use a computer or other service like CoCalc. Do you mean the variables $\lambda_n$ do not commute? That is, $\lambda_1\lambda_2 \neq \lambda_2\lambda_1$? Then you should replace PolynomialRing by FreeAlgebra.

( 2019-08-21 07:51:57 +0200 )edit

Yes, $\lambda_1\lambda_2\neq \lambda_2\lambda_1.$

( 2019-08-21 07:58:09 +0200 )edit

Thank you very much! Now, for example set S_1:=S((1,1,1,3,4)); S_2:=S((1,2,3,4,5)); S_3:=S((1,1,1,6,6)). How to compute S_1+S_2+S_3 (mod 2) in Sage?

( 2019-08-21 08:10:14 +0200 )edit