Two binary forms $f, g \in k[x, y]$ are equivalent when there exists an $M \in GL_2 (k)$ such that $f^M = g$. For simplicity we take $k$ such that $char (k) =0$ and $k=\bar k$.

The equivalence classes of binary forms are determined by the $GL_2 (k)$-invariants and they are known for degree $d \leq 8$ (and possibly $d=9, 10$). Hence, $f$ is equivalent to $g$ if and only if they have the same invariants.

Is there a more efficient way of doing this? Has anybody tried to implement any algorithm to check $GL_2 (k)$-equivalence for binary forms of degree $d > 8$ or for any group $G \leq GL_2 (k)$?

Example: Let $f(x, z)$ be the binary form given by $$f(x, 1)= 442765625 x^6-719030400000 x^5+320847859200000 x^4-64095440076800000 x^3+6360693303410688000 x^2-282590704159256739840 x+3449767488965367037952$$ A simple Maple program by Mark van Hoeji will show that this is equivalent to $$g(x, 1)=28337 x^6-326832 x^5+1035795 x^4-1469600 x^3+1035795 x^2-326832 x+28337$$ Indeed, I know by checking the $GL_2 (\mathbb C)$-invariants $i_1, i_2, i_3$ (see for example this paper among others for their definitions) that $f$ and $g$ are equivalent to $$h(x, 1)= x^5+x^4+x^3+x^2+x.$$

So, my question is if there is any simple approach that would work without using the whole machinery of invariant theory. The main reason that I would like to avoid invariants is that for high degrees we don't know them explicitly.

  • $\begingroup$ You mean if they have the same covariants. I'm sure you know that invariants alone do not distinguish orbits. $\endgroup$ – Abdelmalek Abdesselam Jul 4 '14 at 13:33
  • 1
    $\begingroup$ What do you mean? $GL_2(k)$-invariants determine the orbits (by definition). Whether you call them invariants or covariants from the point of view of classical invariant theory is not important. In any case, my question is if an algorithm can be designed without computing invariants. $\endgroup$ – user24815 Jul 4 '14 at 13:42
  • 1
    $\begingroup$ I don't know about the subgroup case but for GL you can set up the question as an elimination problem since you get a system of algebraic equations in the entries of $M$. I suppose you could try Groebner bases. If you use instead resultants, my guess is that you will end up with invariants/covariants again. BTW, the difference between invariants and covariants is perhaps not important to you, but it certainly was for the people who invented this subject in the 19th century. $\endgroup$ – Abdelmalek Abdesselam Jul 4 '14 at 13:45
  • $\begingroup$ Of course, but that brute force approach would not be that efficient. $\endgroup$ – user24815 Jul 4 '14 at 13:53
  • $\begingroup$ Yes, covariants would be more efficient. Why do you want to avoid them? $\endgroup$ – Abdelmalek Abdesselam Jul 4 '14 at 14:15

It is true that minimal generators for algebras of invariants or covariants of binary forms are not known except for small degree $d$. However, there are plenty of covariants that are known or can be constructed, for any degree, and that should help in separating orbits. To use a metaphor related to current events, deciding to separate orbits without using covariants would be a bit like Germany deciding to take on Brazil without using a goalkeeper.

Anyway, here are two ideas which may help in your search for an efficient algorithm that distinguishes $SL_2$ orbits of binary forms.

  1. You could use the signature curves described in Chapter 8 of the book "Classical Invariant Theory" by Olver. Given a binary form $F$, consider the following covariants, written using transvectants: the hessian $H=(F,F)_2$, the cubicovariant $T=(F,H)_1$ and the degree four covariant $U=(F,T)_1$. The signature curve in $\mathbb{C}^2$ is $$ S=\left\{ \left( \frac{T(p,1)^2}{H(p,1)^3},\frac{U(p,1)}{H(p,1)^2} \right)\ {\rm for}\ p\in\mathbb{C}\ {\rm such\ that}\ H(p,1)\neq 0 \right\}\ . $$ Theorem 8.61 in Olver's book says that two nondegenerate binary forms are equivalent iff their signature curves are equal. Here, nondegenerate means the Hessian is not identically zero, i.e., the form is not a power of a linear form. I suppose one could even visually separate two given inequivalent binary forms by plotting suitable real slices of their signature curves.

  2. You could try to find enough covariants to separate orbits. There has been some activity on finding such separating sets of invariants/covariants. See in particular this paper by Elmer and Kohls. The remarks at the bottom of page 137 of this article seems to indicate that for binary forms the problem is not completely solved yet. Yet it seems more tractable to try to find separating rather than generating sets of covariants.

Finally the answers to MO question Quotient space of $\mathbb{C}^5$ under the action of $SL(2,\mathbb{C})$ may also help.

  • 1
    $\begingroup$ "Germany deciding to take on Brazil without using a goalkeeper." We can wish... $\endgroup$ – Felipe Voloch Jul 8 '14 at 17:12
  • 1
    $\begingroup$ They probably could have gotten away with it without Neuer. $\endgroup$ – user24815 Jul 21 '14 at 23:48

Abdelmalek Abdesselam's suggestion that you try Groebner bases is reasonable for the degre-6 examples that mention in your update to the original question.

Let me spell out the steps explicitly to check whether two forms homogeneous f and g of the same degree in [x,y] are equivalent:

  1. Let $a,b,c,d$ be the matrix-entry coordinates on ${\rm GL}_2$ and consider $f(ax+by,cx+dy)$.

  2. Calculate $f(ax+by,cx+dy)-g(x,y)$ and extract the list $J$ of coefficients of $x^i y^j$. This list represents an ideal in $k[a,b,c,d,t]/(t(ad-bc)-1)$, the coordinate ring of ${\rm GL}_2$. The ideal corresponds to the subscheme of ${\rm GL}_2$ transporting $f$ into $g$, i.e. it gives the conditions on a section of ${\rm GL}_2$ for that section to transform $f$ into $g$.

  3. Compute a Groebner basis of $K = J+[t(ad-bc)-1]$ in $k[a,b,c,d,t]$. If $K$ is not equivalent to $[1]$---if it is not the unit ideal---then there is a section of the transporter over $\overline{k}$ (Nullstellensatz). Computing such a section tells one how to transform $f$ into $g$. If $K$ is equivalent to $[1]$---if it is the unit ideal---then ${\rm GL}_2$ does not transform $f$ into $g$ over $\overline{k}$.

  4. If you would prefer to work with a subgroup scheme $G$ of ${\rm GL}_2$, then add the generators of the ideal defining $G$ to $K$ before computing the Groebner basis.

I tried a pair of your forms, checking that $h(x,y)$ is equivalent to $f(x,y)$. Maple returned the following Groebner basis (lexicographic order t>a>b>c>d) instantly: $$ [d^{12}+2118775924690448809984*d^6+93687714211574708957308664016389973143977984, 5*d^7+14472313805968991556993024*c+96131361823291542077440*d, d^7+20557263928933226643456*b+19226272364658308415488*d, -5*d+704*a, 1039*d^{10}-13614472272996909891715072*d^4+1144692921788849487441900451832894830569062400*t] $$

This Groebner basis tells us to do the following to find the invertible matrix transforming h into f:

a. Solve the following degree-12 equation for $d$: $$ d^{12}+2118775924690448809984d^6+93687714211574708957308664016389973143977984 = 0. $$ Any root is fine.

b. Use the following equation to find $c$ from $d$: $$ 5d^7+96131361823291542077440d +14472313805968991556993024c= 0. $$

c. Use the following equation to find $b$ from $d$: $$ d^7+19226272364658308415488d +20557263928933226643456b= 0. $$

d. Use the following equation to find $a$ from $d$: $$ -5d+704a=0. $$

The transporter scheme is defined over $k$ (which is $\mathbf{Q}$ in this case), and you can use it to study the fields over which $f$ and $h$ are equivalent, if you wish.

I tried the same procedure for transforming $g(x,y)$ into $f(x,y)$ and found that one could construct a matrix for the transformation as follows:

a. Solve the equation $$ d^6-121740744925904896 = 0 $$ to find $d$.

b. Set $c=0$ and $b=0$.

c. Use the equation $$ -5d+704a = 0 $$ to get $a$.

There is another type of transformation matrix with $a=0$ and $d=0$, whose description I omit. (The parameterizing scheme also has degree 6.)

In both cases, we get a degree-12 scheme for the total transporter, since your forms have automorphism group schemes of degree 12. (The transporter, when nonempty, is a bitorsor under the automorphism group schemes of source and target forms.)

This straightforward procedure could become unusable if you had a large number of forms to check or if you wanted to work with forms of higher degree. For studying a few forms of low degree, however, it is both speedy and easy---and it does not require looking up any invariants.

  • $\begingroup$ In my question was stated that I am interested in higher degree binary forms and in a method that is better than using invariants. The brute force method that you suggest here can hardly be called better than using invariants and it has its limitations for higher degree. $\endgroup$ – user24815 Jul 8 '14 at 17:57
  • 1
    $\begingroup$ Perhaps you might explain a bit more about the sort calculations you want to do. Without further details, it is hard to tell what will meet your needs. For the sorts of examples that you mentioned in your question, the straightforward approach seems sufficient. (Similar methods other than Maple's lexicographic order will also be a bit faster.) I tried it with a few examples of higher degree in Maple: checking equivalence was very fast for degrees < 20; by the time I got to degree 30, it took a second or two to check. Is that too slow for your needs? $\endgroup$ – anon Jul 8 '14 at 18:33
  • $\begingroup$ I am wondering if there is an algorithm without using Groebner bases of have to know the set of invariants. I asked for any new ideas or new approaches. $\endgroup$ – user24815 Jul 8 '14 at 19:48

The separating set coincides with the field of semi-invariants and the last can be easy computed in an explicit way for any degree $d.$
Precisely, it generated by elements $$ a_0,z_2,z_3,\ldots,z_d, $$ where $$ z_i:= \sum_{k=0}^{i-2} (-1)^k {i \choose k} a_{i-k} a_1^k a_0^{i-k-1} +(i-1)(-1)^{i+1} a_1^i, i=2,\ldots,d, $$ and $a_i$ are the coefficients of a binary form $$ \sum_{i=0}^d a_i {d \choose i} x^{d-i} y^i. $$ So, you need take two binary forms with equal $a_0$ and just calculate and compare all $z_i$.

Am I wrong?

  • 1
    $\begingroup$ Leox, could you provide some references for the semi-invariants? $\endgroup$ – user24815 Jul 6 '14 at 22:28

From what I have found it seems as the best way to do this is to use an algorithm of Stoll on reducing the binary form. The algorithm is based on Julia's invariant and it is very nice.

For details please see

Reduction theory of point clusters in projective space, Michael Stoll,

Stoll, Michael; Cremona, John E. On the reduction theory of binary forms. J. Reine Angew. Math. 565 (2003), 79–99.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy