Polarization of Homogeneous Polynomials

[Michael Jung]

Dear Sage Developers,

along with characteristic classes, I recently added to the SageManifolds branch, I would like to add their transgression forms now. This, however, involves a polarization of homogeneous polynomials (see https://en.wikipedia.org/wiki/Polarization_of_an_algebraic_form). I wonder whether there are preimplemented algorithms provided in Sage, for instance via Symmetrica or GAP?

Best wishes
Michael

[Markus Wageringel]

Hi Michael,

I do not know about preimplemented algorithms outside Sage itself, but it would not be so difficult to define this map directly. For example, as a map to the free algebra:

sage: T.<u,v,w> = FreeAlgebra(QQ)
sage: R.<x,y,z> = PolynomialRing(QQ)
sage: def _polarize(f):
....:     M = T.indices()
....:     D = {}
....:     for e, c in zip(f.exponents(), f.coefficients()):
....:         c2 = c / multinomial(e)
....:         for p in Permutations(M(list(enumerate(e))).to_list()):
....:             D[M.prod(p)] = c2
....:     return T._from_dict(D)
sage: from sage.categories.morphism import SetMorphism
sage: polarize = SetMorphism(Hom(R, T, Modules(R.base_ring())), _polarize)
sage: polarize(x^2*y + x*y*z)
1/3*u^2*v + 1/3*u*v*u + 1/6*u*v*w + 1/6*u*w*v + 1/3*v*u^2 + 1/6*v*u*w + 1/6*v*w*u + 1/6*w*u*v + 1/6*w*v*u

Now this is a one-sided inverse for symmetrization:

sage: symmetrize = T.module_morphism(on_basis=lambda a: R.prod(R.gen(ai)^ni for ai, ni in a._element_list),
....:                                codomain=R)
sage: f = R.random_element(6, 15)
sage: symmetrize(polarize(f)) == f
True

The main problem with this is the combinatorial complexity, as the output quickly becomes huge for larger input. So it might be better if you can avoid computing this representation explicitly in your use case. After all, all this does is to divide the coefficients by some multinomial coefficient. Nevertheless, I still think this functionality would be useful for small cases and nice to have in Sage.

Alternatively, if you are more interested in viewing this as a multilinear form, then TensorFreeModule may be more suitable. This representation keeps track of symmetries in order to store coefficients without redundancy. Here is a quick example, but there may be room for improvement:

def polarize_form(f):
    n = f.parent().ngens()
    V = FiniteRankFreeModule(f.parent().base_ring(), n, name='V')
    B = V.basis('x')
    from sage.tensor.modules.tensor_free_module import TensorFreeModule
    T = TensorFreeModule(V, (0, n))
    t = T([], name='t', sym=range(n))
    for e, c in zip(f.exponents(), f.coefficients()):
        idx = [j for j, ej in e.sparse_iter() for _ in range(ej)]
        t.set_comp(B)[idx] = c / multinomial(e)
    return t

sage: t = polarize_form(x^2*y + x*y*z)
sage: t.symmetries()
symmetry: (0, 1, 2); no antisymmetry
sage: t.display()
t = 1/3 x_0*x_0*x_1 + 1/3 x_0*x_1*x_0 + 1/6 x_0*x_1*x_2 + 1/6 x_0*x_2*x_1 + 1/3 x_1*x_0*x_0 + 1/6 x_1*x_0*x_2 + 1/6 x_1*x_2*x_0 + 1/6 x_2*x_0*x_1 + 1/6 x_2*x_1*x_0
sage: V = t.base_module()
sage: t(V([0,0,1]), V([1,7,3]), V([1,0,0]))
7/6

Best,

Markus

[Markus Wageringel]

Am Dienstag, 28. April 2020 20:23:01 UTC+2 schrieb Markus Wageringel:

    T = TensorFreeModule(V, (0, n))
    t = T([], name='t', sym=range(n))

There is an error in this code. Here, `n` needs to be replaced by `f.degree()`. 

[Michael Jung]

Hi Markus,

these are awesome pieces of code. Thank you! Unfortunately, I need this as the full polynomial since I have to do different computations with each variable...

Particularly, I have a homogeneous polynomial of matrices and want it to polarize.

Best wishes
MIchael

Am Dienstag, 28. April 2020 20:23:01 UTC+2 schrieb Markus Wageringel:

[Michael Jung]

I wonder, if it is faster to compute the complete polynomial directly or go the way via the free algebra? Anyway, I have to deal with pretty much variables, hence a nice fast algorithm would be nice.

Best Michael