# hspray [![Stack-lts](https://github.com/stla/hspray/actions/workflows/Stack-lts.yml/badge.svg)](https://github.com/stla/hspray/actions/workflows/Stack-lts.yml) [![Stack-nightly](https://github.com/stla/hspray/actions/workflows/Stack-nightly.yml/badge.svg)](https://github.com/stla/hspray/actions/workflows/Stack-nightly.yml) ***Simple multivariate polynomials in Haskell.*** This package deals with multivariate polynomials over a commutative ring, fractions of multivariate polynomials over a commutative field, and multivariate polynomials with symbolic parameters in their coefficients. ____ The main type provided by this package is `Spray a`. An object of type `Spray a` represents a multivariate polynomial whose coefficients are represented by the objects of type `a`. For example: ```haskell import Math.Algebra.Hspray x = lone 1 :: Spray Double y = lone 2 :: Spray Double z = lone 3 :: Spray Double poly = (2 *^ (x^**^3 ^*^ y ^*^ z) ^+^ x^**^2) ^*^ (4 *^ (x ^*^ y ^*^ z)) putStrLn $ prettyNumSpray poly -- 8.0*x^4.y^2.z^2 + 4.0*x^3.y.z ``` This is the easiest way to construct a spray: first introduce the polynomial variables with the `lone` function, and then combine them with arithmetic operations. There are numerous functions to print a spray. If you don't like the letters `x`, `y`, `z` in the output of `prettyNumSpray`, you can use `prettyNumSprayXYZ` to change them to whatever you want: ```haskell putStrLn $ prettyNumSprayXYZ ["A","B","C"] poly -- 8.0*A^4.B^2.C^2 + 4.0*A^3.B.C ``` Note that this function does not throw an error if you don't provide enough letters; in such a situation, it takes the first given letter and it appends it with the digit `i` to denote the `i`-th variable: ```haskell putStrLn $ prettyNumSprayXYZ ["A","B"] poly -- 8.0*A1^4.A2^2.A3^2 + 4.0*A1^3.A2.A3 ``` This is the same output as the one of `prettyNumSprayX1X2X3 "A" poly`. More generally, one can use the type `Spray a` as long as the type `a` has the instances `Eq` and `Algebra.Ring` (defined in the **numeric-prelude** library). For example `a = Rational`: ```haskell import Math.Algebra.Hspray import Data.Ratio x = lone 1 :: QSpray -- QSpray = Spray Rational y = lone 2 :: QSpray z = lone 3 :: QSpray poly = ((2%3) *^ (x^**^3 ^*^ y ^*^ z) ^-^ x^**^2) ^*^ ((7%4) *^ (x ^*^ y ^*^ z)) putStrLn $ prettyQSpray poly -- (7/6)*x^4.y^2.z^2 - (7/4)*x^3.y.z ``` Or `a = Spray Double`: ```haskell import Math.Algebra.Hspray alpha = lone 1 :: Spray Double x = lone 1 :: Spray (Spray Double) y = lone 2 :: Spray (Spray Double) poly = ((alpha *^ x) ^+^ (alpha *^ y))^**^2 showSprayXYZ' (prettyNumSprayXYZ ["alpha"]) ["x","y"] poly -- (alpha^2)*x^2 + (2.0*alpha^2)*x.y + (alpha^2)*y^2 ``` We will come back to these sprays of type `Spray (Spray a)`. They can be used to represent parametric polynomials. #### Evaluation of a spray: ```haskell import Math.Algebra.Hspray x = lone 1 :: Spray Double y = lone 2 :: Spray Double z = lone 3 :: Spray Double spray = 2 *^ (x ^*^ y ^*^ z) -- evaluate spray at x=2, y=1, z=2 evalSpray spray [2, 1, 2] -- 8.0 ``` #### Partial evaluation: ```haskell import Math.Algebra.Hspray import Data.Ratio x1 = lone 1 :: Spray Rational x2 = lone 2 :: Spray Rational x3 = lone 3 :: Spray Rational spray = x1^**^2 ^+^ x2 ^+^ x3 ^-^ unitSpray putStrLn $ prettyQSprayX1X2X3 "x" spray -- x1^2 + x2 + x3 - 1 -- -- substitute x1 -> 2 and x3 -> 3, and don't substitute x2 spray' = substituteSpray [Just 2, Nothing, Just 3] spray putStrLn $ prettyQSprayX1X2X3 "x" spray' -- x2 + 6 ``` #### Differentiation of a spray: ```haskell import Math.Algebra.Hspray x = lone 1 :: Spray Double y = lone 2 :: Spray Double z = lone 3 :: Spray Double spray = 2 *^ (x ^*^ y ^*^ z) ^+^ (3 *^ x^**^2) putStrLn $ prettyNumSpray spray -- 3.0*x^2 + 2.0*x.y.z -- -- derivative with respect to x putStrLn $ prettyNumSpray $ derivative 1 spray -- 6.0*x + 2.0*y.z" ``` ## Gröbner bases As of version 2.0.0, it is possible to compute a Gröbner basis of the ideal generated by a list of spray polynomials. One of the numerous applications of Gröbner bases is the *implicitization* of a system of parametric equations. That means that they allow to get an implicit equation equivalent to a given set of parametric equations, for example an implicit equation of a parametrically defined surface. Let us give an example of implicitization for an *Enneper surface*. Here are the parametric equations of this surface: ```haskell import Math.Algebra.Hspray import Data.Ratio ( (%) ) u = qlone 1 v = qlone 2 x = 3*^u ^+^ 3*^(u ^*^ v^**^2) ^-^ u^**^3 y = 3*^v ^+^ 3*^(u^**^2 ^*^ v) ^-^ v^**^3 z = 3*^u^**^2 ^-^ 3*^v^**^2 ``` The first step of the implicitization is to compute a Gröbner basis of the following list of polynomials: ```haskell generators = [x ^-^ qlone 3, y ^-^ qlone 4, z ^-^ qlone 5] ``` Once the Gröbner basis is obtained, one has to identify which of its elements do not involve the first two variables (`u` and `v`): ```haskell gbasis = groebnerBasis generators True isFreeOfUV :: QSpray -> Bool isFreeOfUV p = not (involvesVariable p 1) && not (involvesVariable p 2) freeOfUV = filter isFreeOfUV gbasis ``` Then the implicit equations (there can be several ones) are obtained by removing the first two variables from these elements: ```haskell results = map (dropVariables 2) freeOfUV ``` Here we find only one implicit equation (i.e. `length results` is `1`). We only partially display it because it is long: ```haskell implicitEquation = results !! 0 putStrLn $ prettyQSpray implicitEquation -- x^6 - 3*x^4.y^2 + (5/9)*x^4.z^3 + 6*x^4.z^2 - 3*x^4.z + 3*x^2.y^4 + ... ``` Let us check it is correct. We take a point on the Enneper surface, for example the point corresponding to $u=1/4$ and $v=2/3$ ($u$ and $v$ range from $0$ to $1$): ```haskell xyz = map (evaluateAt [1%4, 2%3]) [x, y, z] ``` If the implicitization is correct, then the polynomial `implicitEquation` should be zero at any point on the Enneper surface. This is true for our point: ```haskell evaluateAt xyz implicitEquation == 0 -- True ``` In the [unit tests](https://github.com/stla/hspray/blob/main/tests/Main.hs), you will find a more complex example of implicitization: the implicitization of the ellipse parametrically defined by $x = a \cos t$ and $y = b \sin t$. It is more complex because there are the parameters $a$ and $b$ and because one has to use the relation ${(\cos t)}^2 + {(\sin t)}^2 = 1$. ## Easier usage To construct a spray using the ordinary symbols `+`, `-`, `*` and `^`, one can hide these operators from **Prelude** and import them from the **numeric-prelude** library; constructing a spray in this context is easier: ```haskell import Prelude hiding ((+), (-), (*), (^), (*>), (<*)) import qualified Prelude as P import Algebra.Additive import Algebra.Module import Algebra.Ring import Math.Algebra.Hspray import Data.Ratio x = lone 1 :: QSpray y = lone 2 :: QSpray z = lone 3 :: QSpray spray = ((2%3) *^ (x^**^3 ^*^ y ^*^ z) ^-^ x^**^2) ^*^ ((7%4) *^ (x ^*^ y ^*^ z)) spray' = ((2%3) *^ (x^3 * y * z) - x^2) * ((7%4) *^ (x * y * z)) spray == spray' -- True ``` Note that `*>` could be used instead of `*^` but running `lambda *> spray` possibly throws an "ambiguous type" error regarding the type of `lambda`. Maybe better (I didn't try yet), follow the "Usage" section on the [Hackage page](https://hackage.haskell.org/package/numeric-prelude-0.4.4#usage) of **numeric-prelude**. ## Symbolic parameters in the coefficients Assume you have the polynomial `a * (x² + y²) + 2b/3 * z`, where `a` and `b` are symbolic rational numbers. You can represent this polynomial by a `Spray (Spray Rational)` spray as follows: ```haskell import Prelude hiding ((*), (+), (-), (^)) import qualified Prelude as P import Algebra.Additive import Algebra.Ring import Math.Algebra.Hspray x = lone 1 :: Spray (Spray Rational) y = lone 2 :: Spray (Spray Rational) z = lone 3 :: Spray (Spray Rational) a = lone 1 :: Spray Rational b = lone 2 :: Spray Rational spray = a *^ (x^2 + y^2) + ((2 *^ b) /^ 3) *^ z putStrLn $ showSprayXYZ' (prettyQSprayXYZ ["a","b"]) ["X","Y","Z"] spray -- (a)*X^2 + (a)*Y^2 + ((2/3)*b)*Z ``` You can extract the powers and the coefficients as follows: ```haskell l = toList spray map fst l -- [[0,0,1],[2],[0,2]] map toList $ map snd l -- [[([0,1],2 % 3)],[([1],1 % 1)],[([1],1 % 1)]] ``` These `Spray (Spray a)` sprays can be very useful. They represent polynomials whose coefficients polynomially depend on some parameters. Actually there is a type alias of `Spray (Spray a)` in **hspray**, namely `SimpleParametricSpray a`, and there are some convenient functions to deal with sprays of this type. There is also a type alias of `SimpleParametricSpray Rational`, namely `SimpleParametricQSpray`. For example we can print our `SimpleParametricQSpray` spray `spray` as follows: ```haskell putStrLn $ prettySimpleParametricQSprayABCXYZ ["a","b"] ["X","Y","Z"] spray -- { a }*X^2 + { a }*Y^2 + { (2/3)*b }*Z ``` The [Gegenbauer polynomials](https://en.wikipedia.org/wiki/Gegenbauer_polynomials) are a real-life example of polynomials that can be represented by `SimpleParametricQSpray` sprays. They are univariate polynomials whose coefficients polynomially depend on a parameter $\alpha$ (the polynomial dependency is clearly visible from the recurrence relation given on Wikipedia). Here is their recursive implementation in **hspray**: ```haskell gegenbauerPolynomial :: Int -> SimpleParametricQSpray gegenbauerPolynomial n | n == 0 = unitSpray | n == 1 = (2.^a) *^ x | otherwise = (2.^(n'' ^+^ a) /^ n') *^ (x ^*^ gegenbauerPolynomial (n - 1)) ^-^ ((n'' ^+^ 2.^a ^-^ unitSpray) /^ n') *^ gegenbauerPolynomial (n - 2) where x = lone 1 :: SimpleParametricQSpray a = lone 1 :: QSpray n' = toRational n n'' = constantSpray (n' - 1) ``` Let's try it: ```haskell n = 3 g = gegenbauerPolynomial n putStrLn $ prettySimpleParametricQSprayABCXYZ ["alpha"] ["X"] g -- { (4/3)*alpha^3 + 4*alpha^2 + (8/3)*alpha }*X^3 + { -2*alpha^2 - 2*alpha }*X ``` Let's check the differential equation given in the Wikipedia article: ```haskell g' = derivative 1 g g'' = derivative 1 g' alpha = lone 1 :: QSpray x = lone 1 :: SimpleParametricQSpray nAsSpray = constantSpray (toRational n) shouldBeZero = (unitSpray ^-^ x^**^2) ^*^ g'' ^-^ (2.^alpha ^+^ unitSpray) *^ (x ^*^ g') ^+^ n.^(nAsSpray ^+^ 2.^alpha) *^ g putStrLn $ prettySpray shouldBeZero -- 0 ``` Now, how to substitute a value to the parameter $\alpha$? For example, it is said in the Wikipedia article that this yields the Legendre polynomials for $\alpha = 1/2$. The package provides the function `substituteParameters` to perform this task: ```haskell import Data.Ratio (%) putStrLn $ prettyQSpray'' $ substituteParameters g [1%2] -- (5/2)*X^3 - (3/2)*X ``` This is a `Spray Rational` spray. The Wikipedia article also provides the value at $1$ of the Gegenbauer polynomials in function of $\alpha$. We can get this value with `evalParametricSpray`: ```haskell putStrLn $ prettyQSprayXYZ ["alpha"] $ evalParametricSpray g [1] -- (4/3)*alpha^3 + 2*alpha^2 + (2/3)*alpha ``` This is also a `Spray Rational` spray. ## Ratios of sprays and general parametric sprays Since you have just seen that the type `Spray (Spray a)` is named `SimpleParametricSpray a`, you probably guessed there is also a more general type named `ParametricSpray a`. Yes, and this is an alias of `Spray (RatioOfSprays a)`, where the type `RatioOfSprays a` has not been discussed yet. The objects of this type represent fractions of multivariate polynomials and so this type is a considerable enlargment of the `Spray a` type. Thus the `Spray (RatioOfSprays a)` sprays can represent multivariate polynomials whose coefficients depend on some parameters, with a dependence described by a fraction of polynomials in these parameters. Let's start with a short presentation of the ratios of sprays. ### The `RatioOfSprays` type The type `RatioOfSprays a`, whose objects represent ratios of sprays, has been introduced in version 0.2.7.0. To construct a ratio of sprays, apply `%//%` between its numerator and its denominator: ```haskell import Math.Algebra.Hspray x = qlone 1 -- shortcut for lone 1 :: Spray Rational y = qlone 2 rOS = (x ^-^ y) %//% (x^**^2 ^-^ y^**^2) putStrLn $ prettyRatioOfQSprays rOS -- [ 1 ] %//% [ x + y ] ``` The `%//%` operator always returns an *irreducible fraction*. If you are ***sure*** that your numerator and your denominator are coprime, you can use the `%:%` instead, to gain some efficiency. But if they are not coprime, this can have unfortunate consequences. The `RatioOfSprays a` type makes sense when `a` has a field instance, and then it has a field instance too. To use the field operations, import the necessary modules from **numeric-prelude**, and hide these operations from the `Prelude` module; then you can also use the **numeric-prelude** operations for sprays, instead of using `^+^`, `^-^`, `^*^`, `^**^`: ```haskell import Prelude hiding ((+), (-), (*), (/), (^), (*>), (<*)) import qualified Prelude as P import Algebra.Additive import Algebra.Module import Algebra.RightModule import Algebra.Ring import Algebra.Field import Math.Algebra.Hspray x = qlone 1 y = qlone 2 p = x^2 - 3*^(x * y) + y^3 q = x - y rOS1 = p^2 %//% q rOS2 = rOS1 + unitRatioOfSprays rOS = rOS1^2 + rOS1*rOS2 - rOS1/rOS2 + rOS2 -- slow! (rOS1 + rOS2) * (rOS1 - rOS2) == rOS1^2 - rOS2^2 -- True rOS / rOS == unitRatioOfSprays -- True ``` Actually, as of version 0.5.0.0, it is possible to apply the operations `^+^`, `^-^`, `^*^`, `^**^` and `*^` to the ratios of sprays. The `RatioOfSprays a` type also has left and right module instances over `a` and over `Spray a` as well. That means you can multiply a ratio of sprays by a scalar and by a spray, by using, depending on the side, either `*>` or `<*`: ```haskell import Data.Ratio ( (%) ) rOS' = (3%4::Rational) *> rOS^2 + p *> rOS ``` You can also divide a ratio of sprays by a spray with `%/%`: ```haskell p *> (rOS' %/% p) == rOS' -- True rOS1 %/% p == p %//% q -- True ``` When `a` has a field instance, both a `Spray a` spray and a `RatioOfSprays a` ratio of sprays can be divided by a scalar with the `/>` operator: ```haskell k = 3 :: Rational (p /> k) *> rOS == p *> (rOS /> k) -- True ``` Use `evalRatioOfSprays` to evaluate a ratio of sprays: ```haskell import Data.Ratio ( (%) ) f :: Algebra.Field.C a => a -> a -> a f u v = u^2 + u*v - u/v + v rOS == f rOS1 rOS2 -- True values = [2%3, 7%4] r1 = evalRatioOfSprays rOS1 values r2 = evalRatioOfSprays rOS2 values evalRatioOfSprays rOS values == f r1 r2 -- True ``` ### The `ParametricSpray` type Recall that `SimpleParametricSpray a = Spray (Spray a)` and `ParametricSpray a = Spray (RatioOfSprays a)`, and we have the aliases `SimpleParametricQSpray = SimpleParametricSpray Rational` and `ParametricQSpray = ParametricSpray Rational`. The functions `substituteParameters` and `evalParametricSpray`, that we previously applied to a `SimpleParametricSpray a` spray, are also applicable to a `ParametricSpray a` spray. We didn't mention the function `changeParameters` yet, which is also applicable to these two types of parametric sprays. This function performs some polynomial transformations of the parameters of a parametric spray. For example, consider the [Jacobi polynomials](https://en.wikipedia.org/wiki/Jacobi_polynomials). They are univariate polynomials with two parameters $\alpha$ and $\beta$. They are implemented in **hspray** as `ParametricQSpray` sprays. In fact it seems that the coefficients of the Jacobi polynomials *polynomially* depend on $\alpha$ and $\beta$, and if this is true one could implement them as `SimpleParametricQSpray` sprays. I will come back to this point later. The recurrence relation defining the Jacobi polynomials involves a division which makes the type `ParametricQSpray` necessary anyway. The `changeParameters` function is useful to derive the Gegenbauer polynomials from the Jacobi polynomials. Indeed, as asserted in the Wikipedia article, the Gegenbauer polynomials coincide, up to a factor, with the Jacobi polynomials with parameters $\alpha - 1/2$ and $\alpha - 1/2$. Here is how to apply the `changeParameters` function to get this special case of Jacobi polynomials: ```haskell import Data.Ratio ( (%) ) j = jacobiPolynomial 3 alpha = qlone 1 alpha' = alpha ^-^ constantSpray (1%2) j' = changeParameters j [alpha', alpha'] ``` Now let's come back to the conjecture claiming that the coefficients of the Jacobi polynomials *polynomially* depend on $\alpha$ and $\beta$, and thus these polynomials can be represented by `SimpleParametricQSpray` sprays. Maybe this can be deduced from a formula given in the Wikipedia article, I didn't spend some time on this problem. I made this conjecture because I observed this fact for some small values of $n$, and I tried the function `canCoerceToSimpleParametricSpray` for other values, which always returned `True`. One can apply the function `asSimpleParametricSpray` to perform the coercion. ## The `OneParameterSpray` type There is a third type of parametric sprays in the package, namely the `OneParameterSpray` sprays. The objects of this type represent multivariate polynomials whose coefficients are fractions of polynomials *in only one variable* (the parameter). So they are less general than the `ParametricSpray` sprays. These sprays are no longer very useful. They have been introduced in version 0.2.5.0 and this is the first type of parametric sprays that has been provided by the package. When the more general `ParametricSpray` sprays have been introduced, I continued to develop the `OneParameterSpray` sprays because they were more efficient than the univariate `ParametricSpray` sprays. But as of version 0.4.0.0, this is no longer the case. This is what I concluded from some benchmarks on the *Jack polynomials*, implemented in the [**jackpolynomials** package](https://github.com/stla/jackpolynomials). These are sprays of type `Spray (RatioOfPolynomials a)`, where the type `RatioOfPolynomials a` deals with objects that represent fractions of *univariate* polynomials. The type of these univariate polynomials is `Polynomial a`. The functions we have seen for the simple parametric sprays and the parametric sprays, `substituteParameters`, `evalParametricSpray`, and `changeParameters`, are also applicable to the one-parameter sprays. The `OneParameterSpray` sprays were used in the [**jackpolynomials** package](https://github.com/stla/jackpolynomials) to represent the Jack polynomials with a symbolic Jack parameter but they have been replaced with the `ParametricSpray` sprays. ## Other features Other features offered by the package include: resultant and subresultants of two polynomials, Sturm-Habicht sequence of a polynomial, number of real roots of a univariate polynomial, and greatest common divisor of two polynomials with coefficients in a field.