qetaicat.spad

-------------------------------------------------------------------
---
--- FriCAS QEta
--- Copyright (C) 2015-2021  Ralf Hemmecke <ralf@hemmecke.org>
---
-------------------------------------------------------------------
-- This program is free software: you can redistribute it and/or modify
-- it under the terms of the GNU General Public License as published by
-- the Free Software Foundation, either version 3 of the License, or
-- (at your option) any later version.
--
-- This program is distributed in the hope that it will be useful,
-- but WITHOUT ANY WARRANTY; without even the implied warranty of
-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-- GNU General Public License for more details.
--
-- You should have received a copy of the GNU General Public License
-- along with this program.  If not, see <http://www.gnu.org/licenses/>.
-------------------------------------------------------------------

OF==>OutputForm
display77(x) ==> display((x::OF)::Formatter(Format1D))
yof x ==> x :: Symbol :: OF
dbgPrint(x,y) ==> display77([yof ":> ", yof x, y::OF]$List(OF))
tracePrint(x,y) ==> display77(hconcat([yof"-- ",yof x,yof":=",y::OF]$List(OF)))

)if LiterateDoc
\documentclass{article}
\usepackage{qeta}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}
\title{Computation of Polynomial Relations among Dedekind Eta
  Functions}
\author{Ralf Hemmecke}
\date{10-Dec-2015}
\maketitle

\begin{abstract}
  Based on articles by Hemmecke and Radu, we compute relations among
  eta-functions of a given level $N$. We provide several variants of
  this computation. The category \qetatype{QEtaIdealCategory} is an
  attempt to abstract identical code. The main difference of the
  variants is in the computation of generators of the ideal of
  relations among eta-quotients. The variants in the files
  \PathName{qetair.spad} and \PathName{qetais.spad} are no longer
  maintained

  The code implements (as a default package of the category) the
  computation of polynomial relations among eta-functions as
  described in \cite{HemmeckeRadu_EtaRelations_2019}. The computation
  is done in various sub-steps building upon the known generators of
  the monoid of all eta-quotients of a certain level, see file
  \PathName{qetaqmspec.spad}.
  \begin{itemize}
  \item \qetafun{etaQuotientIdealGenerators}{QEtaIdealCategory}
    computes generators of the ideal of all relations among
    eta-quotients. The result corresponds to $H^{(M)}$ from
    \cite[Chapter~7]{HemmeckeRadu_EtaRelations_2019}.
  \item \qetafun{etaLaurentIdealGenerators}{QEtaIdealCategory}
    substitutes the $E_\delta$ and $Y_\delta$ variables into the
    relations obtained from the previous step, this function returns
    $\chi'(H^L)\cup U$ as described in
    \cite[Chapter~7]{HemmeckeRadu_EtaRelations_2019}
  \item \qetafun{etaRelations}{QEtaIdealCategory} computes a \GB{} of
    the polynomials from the previous step and returns the polynomial
    that are only in the $E$ variables.
  \end{itemize}
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\tableofcontents

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Overview}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

This code is based on \cite{HemmeckeRadu_EtaRelations_2019}. In fact,
the following code was used to develop the results of this article.

The code here is very close to what is written in
\cite{HemmeckeRadu_EtaRelations_2019}, \ie, from a list of generators
of $R^\infty(N)$ we compute generators of the ideal $J^{(M)}$ by the
function \code{etaQuotientIdealGenerators}.

Then \code{etaLaurentIdealGenerators} substitutes the $M$ variables by
the $E$ and $Y$ variables so that eventually we have $\chi'(H^L)\cup
U$ in the notation of \cite{HemmeckeRadu_EtaRelations_2019}.

Eventually, the function, \code{etaRelations} takes the output of
\code{etaLaurentIdealGenerators} and eliminates the $Y$ variables by
computing a \GB{} with respect to block order, separately degrevlex in
the $Y$ and $E$ variables.

The variants to compute the generators of $J^{(M)}$ are abstracted
into the function \code{relationsIdealGenerators}, which is
implemented in the respective package.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Implementation}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Helper macros}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Let us start with a few common macros.

These two technical macros are necessary to distinguish between Rep
and \%.
)endif

rep x ==> (x@%) pretend Rep
per x ==> (x@Rep) pretend %

)if LiterateDoc
Now some abbreviations for common domains.
)endif

PP ==> PositiveInteger
NN ==> NonNegativeInteger
ZZ ==> Integer
LZZ ==> List ZZ
LLZZ ==> List LZZ
INDICES ==> LLZZ
EQI C  ==> EtaQuotientInfinity C

asNN x ==> x pretend NN
asPP x ==> x pretend PP

mSPECSInfMOD ==> etaQuotientMonoidInfinitySpecifications _
                   $ QEtaQuotientSpecifications4ti2(QMOD)
specMODA1 C ==> _
  modularEtaQuotientInfinity $ QEtaModularInfinityExpansion(C, QMOD)

)if LiterateDoc
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Category QEtaIdealCategory: Relations among Dedekind
  eta-functions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
)endif

)abbrev category QETAIDC QEtaIdealCategory
++ QEtaIdealCategory(C) is a category that implements a number of
++ functions connected to relations among Dedekind eta-functions. It
++ allows for differend implementation of the function
++ relationsIdealGenerator, which does the main job of computing the
++ generators of the ideal of relations of modular eta-quotients
++ having a pole at most at infinity.
QEtaIdealCategory(C, QMOD): Category == Exports where
  C: EuclideanDomain
  QMOD: QEtaModularCategory
  A1 C ==> Finite0Series C --: Join(QEtaLaurentSeriesCategory C, QEtaAlgebra C)
  Pol ==> Polynomial C
  LPol ==> List Pol
  SPEC ==> QEtaSpecification
  SPECS ==> List SPEC
  Exports ==> with
    algebraicRelations: (INDICES, LPol, Character) -> LPol
        ++ algebraicRelations(idxs, eqrels, c) returns
        ++ relations among the variables in eqrels that start with
        ++ the character c. Here eqrels is supposed to be a list of
        ++ polynomial in Ei, Yi, and Mi variables.
    etaLaurentIdealGenerators: (PP, INDICES) -> LPol
        ++ etaLaurentIdealGenerators(nn,idxs) computes generators for
        ++ the ideal of eta-functions and their inverses given by the
        ++ indices having no poles at the cusps given through QMOD
        ++ except at infinity. These eta-quotient generators are then
        ++ expressed in Ei and Yi variables where Ei stands for the
        ++ eta-function with index i and Yi for its inverse.
        ++ Additionally relations of the form Ei*Yi-1 are added to
        ++ include the relations among the Ei and Yi variables.
    etaLaurentIdealGenerators: (INDICES, SPECS, LPol) -> LPol
        ++ etaLaurentIdealGenerators(idxs,mspecs,eqigens) returns the
        ++ concatenation of the lists returned by
        ++ etaLaurentIdealLists(idxs,mspecs,eqigens).
    etaLaurentIdealLists: (INDICES, SPECS, LPol) -> List LPol
        ++ etaLaurentIdealLists(idxs,mspecs,eqigens) assumes that
        ++ eqigens are generators for the ideal of all relations among
        ++ the eta-quotients given by mspecs. The i-th entry of mspecs
        ++ should be represented in eqigens by the variable Mi. The
        ++ function simplifies Ei*Yi to 1 for any index i appearing in
        ++ idxs. In that sense the function returns the generators of
        ++ the ideal of all relations among generalized eta-functions
        ++ and their inverses. The result is a two element list where
        ++ the first entry is given by the trivial relations Ei*Yi-1
        ++ and the second list are the polynomials as described above.
    etaQuotientIdealGenerators: SPECS -> LPol
        ++ etaQuotientIdealGenerators(mspecs) returns polynomials in
        ++ the variables M_i (where i runs from 1 to #mspecs) that
        ++ generate the ideal of all relations of the eta-quotients
        ++ given by mspecs. Originally it was intended that mspecs is
        ++ the specifications of the eta-quotients given by
        ++ etaQuotientMonoidSpecifications(level) from the package
        ++ \spadtype{QEtaQuotientSpecifications4ti2}. This function
        ++ just sets up a the q-series and then calls
        ++ relationsIdealGenerators on these series.
    etaQuotientMonomial: SPEC -> Pol
        ++ etaQuotientMonomial(spec) returns
        ++ etaQuotientMonomial(spec, char "E", char "Y").
    etaQuotientMonomial: (SPEC, Character, Character) -> Pol
        ++ etaQuotientMonomial(spec, e, y) translates the
        ++ specification of a generalized eta-quotient to a monomial.
        ++ The indices i are translated into a variable via
        ++ indexedSymbol(e,i) if the exponent is positive and to
        ++ indexedSymbol(y,i) if the exponent is negative. All those
        ++ variables with their (absolute) value of) the exponent are
        ++ multiplied together to give the resulting monomial.
    etaRelations: INDICES -> LPol
        ++ etaRelations(idxs) returns algebraic relations
        ++ among the generalized eta-function given by the indices
        ++ idxs.
    etaRelations: (INDICES, LPol) -> LPol
        ++ etaRelations(idxs,eligens) eliminates the Y variables from
        ++ the input and returns the resulting Groebner basis. It is
        ++ assumed that eligens is a list of polynomials in Ei and Yi
        ++ variables where the indices i are given by idxs.
    laurentRelations: (List Symbol, List Symbol) -> LPol
        ++ laurentRelations(esyms, ysyms) returns
        ++ [e*y-1 for e in esyms for y in ysyms].
    relationsIdealGenerators: List A1 C -> LPol
        ++ relationsIdealGenerators(qseries) returns
        ++ a set of generators in the variables M_i of the ideal
        ++ of all relations among the given qseries.
        ++ The initial series correspond to the variables M_i in the output
        ++ of this function.
        ++ We assume that qseries is a list of Laurent series in q that
        ++ correspond to modular functions for $\Gamma_0(N)$ having a pole
        ++ (if any) at infinity only.
        ++ The samba algorithm can be used in its extended form in order to
        ++ also get a representation of resulting algebra basis in terms
        ++ of the original elements.
        ++ Algoritm samba is described in: Ralf Hemmecke,
        ++ "Dancing Samba with Ramanujan Partition Congruences",
        ++ Journal of Symbolic Computation, 84, 2018.
        ++ See \cite{HemmeckeRadu_EtaRelations_2019} for more detail
        ++ and the package \spadtype{QEtaIdealHemmecke}.
   add
    -- geqrels are polynomials in fi and Ei, Yi, Mj. Here we assume
    -- that Fi=fi*cofactor(Ei,Yi) and the Mj represent eta-quotients.
    algebraicRelations(_
      idxs: INDICES, geqrels: LPol, c: Character): LPol ==
        nn: PP := asPP lcm [first x for x in idxs]
        mspecs: SPECS := mSPECSInfMOD(nn, idxs)
        eqigens: LPol := etaQuotientIdealGenerators mspecs
        igens := concat(eqigens, geqrels)
        gens := etaLaurentIdealGenerators(idxs, mspecs, igens)
        ysyms: List Symbol := indexedSymbols("Y", idxs)$QAuxiliaryTools
        esyms: List Symbol := indexedSymbols("E", idxs)$QAuxiliaryTools
        fvars := [[x for x in variables p | (string x).1 = c] for p in geqrels]
        fsyms: List Symbol := removeDuplicates concat fvars
        syms: List Symbol := concat [ysyms, esyms, fsyms]
        dim: NN := # syms
        dim1: NN := # esyms + # ysyms -- want to eliminate those
        E ==> SplitHomogeneousDirectProduct(dim, dim1, NN)
        gb := groebner(gens, syms)$QEtaGroebner(C, E)
        -- take only the polys that do not invole any Y variable
        xPolynomials(gb, c)$PolynomialTool(C)

    etaLaurentIdealGenerators(nn: PP, idxs: INDICES): LPol ==
        mspecs: SPECS := mSPECSInfMOD(nn, idxs)
        eqigens: LPol := etaQuotientIdealGenerators mspecs
        etaLaurentIdealGenerators(idxs, mspecs, eqigens)

    etaLaurentIdealGenerators(_
      idxs: INDICES, mspecs: SPECS, eqigens: LPol): LPol ==
        concat etaLaurentIdealLists(idxs, mspecs, eqigens)

    etaLaurentIdealLists(_
      idxs: INDICES, mspecs: SPECS, igens: LPol): List LPol ==
        -- Substitute the polynomials given by mspecs for the
        -- respective Mi variables. Leave other variables as they are.
        PE ==> PolynomialEvaluation(C, Pol)
        geqMonomials := [etaQuotientMonomial mspec for mspec in mspecs]
        msyms: List Symbol := indexedSymbols("M", #mspecs)$QAuxiliaryTools
        vars: List Symbol := concat [variables x for x in igens]
        -- As an extension we allow a polynomial in igens to contain
        -- other variables than just the Mi
        fsyms: List Symbol := setDifference(vars, msyms) -- remove the Mi
        fc(c: C): Pol == c::Pol
        vals: LPol := concat([f::Pol for f in fsyms], geqMonomials)
        syms := concat(fsyms, msyms)
        gens: LPol := [eval(x, fc, syms, vals)$PE for x in igens]
        -- now reduce modulo E*Y=1.
        ysyms: List Symbol := indexedSymbols("Y", idxs)$QAuxiliaryTools
        esyms: List Symbol := indexedSymbols("E", idxs)$QAuxiliaryTools
        yerels: LPol := laurentRelations(esyms, ysyms)
        -- make sure that there are no Ei and Yi in fsyms
        yesyms := concat(ysyms, esyms)
        syms := concat(yesyms, setDifference(fsyms, yesyms))
        dim: NN := # syms
        dim1: NN := # ysyms
        E ==> SplitHomogeneousDirectProduct(dim, dim1, NN)
        nfs: LPol := normalForms(gens, yerels, syms)$QEtaGroebner(C, E)
        [yerels, nfs]

    etaQuotientIdealGenerators(mspecs: SPECS): LPol ==
        egens: List A1 C := [specMODA1(C) spec for spec in mspecs]
        relationsIdealGenerators egens

    etaQuotientMonomial(mspec: SPEC): Pol ==
        etaQuotientMonomial(mspec, char "E", char "Y")

    etaQuotientMonomial(mspec: SPEC, pv: Character, nv: Character): Pol ==
        iSY(c,i) ==> indexedSymbol(c::String, i) $ QAuxiliaryTools
        p: Pol := 1
        for l in parts mspec repeat
            e := specExponent l
            i: List ZZ := specIndex l
            e > 0 => p := p * monomial(1$Pol, iSY(pv, i), asNN e)
            e < 0 => p := p * monomial(1$Pol, iSY(nv, i), asNN abs e)
        return p

    etaRelations(idxs: INDICES): LPol ==
        nn: PP := asPP lcm [first x for x in idxs]
        etaRelations(idxs, etaLaurentIdealGenerators(nn, idxs))

    etaRelations(idxs: INDICES, eligens: LPol): LPol ==
        -- We only need to eliminate the Y_d variables from the
        -- etaLaurentIdealGenerators.
        ysyms: List Symbol := indexedSymbols("Y", idxs)$QAuxiliaryTools
        esyms: List Symbol := indexedSymbols("E", idxs)$QAuxiliaryTools
        syms: List Symbol := concat(ysyms, esyms)
        dim: NN := # syms
        dim1: NN := # ysyms
        E ==> SplitHomogeneousDirectProduct(dim, dim1, NN)
        gb := groebner(eligens, syms)$QEtaGroebner(C, E)
        -- take only the polys that do not invole any Y variable
        xPolynomials(gb, char "E")$PolynomialTool(C)

    laurentRelations(esyms: List Symbol, ysyms: List Symbol): LPol ==
        [monomial(1$Pol, [e, y], [1, 1]) - 1$Pol for e in esyms for y in ysyms]

)if LiterateDoc
\end{document}
)endif