\relax 
\providecommand\hyper@newdestlabel[2]{}
\providecommand\HyperFirstAtBeginDocument{\AtBeginDocument}
\HyperFirstAtBeginDocument{\ifx\hyper@anchor\@undefined
\global\let\oldcontentsline\contentsline
\gdef\contentsline#1#2#3#4{\oldcontentsline{#1}{#2}{#3}}
\global\let\oldnewlabel\newlabel
\gdef\newlabel#1#2{\newlabelxx{#1}#2}
\gdef\newlabelxx#1#2#3#4#5#6{\oldnewlabel{#1}{{#2}{#3}}}
\AtEndDocument{\ifx\hyper@anchor\@undefined
\let\contentsline\oldcontentsline
\let\newlabel\oldnewlabel
\fi}
\fi}
\global\let\hyper@last\relax 
\gdef\HyperFirstAtBeginDocument#1{#1}
\providecommand*\HyPL@Entry[1]{}
\HyPL@Entry{0<</S/D>>}
\@writefile{toc}{\contentsline {section}{\numberline {1}Motivation and main results}{2}{section.1}}
\newlabel{eq:theta}{{1}{2}{Motivation and main results}{equation.1.1}{}}
\newlabel{eq:thetatri}{{2}{2}{Motivation and main results}{equation.1.2}{}}
\citation{Mumford83}
\citation{Mumford84}
\citation{Mumford91}
\citation{Weber08}
\citation{Schertz02}
\citation{EnSc04}
\citation{EnSc13}
\citation{EnMo14}
\citation{Euler83}
\citation{Euler83}
\citation{Weber08}
\citation{Weber08}
\citation{Weber08}
\citation{Rademacher38}
\citation{Enge09cla}
\citation{Enge09mod}
\newlabel{eq:etapenta}{{3}{3}{Motivation and main results}{equation.1.3}{}}
\citation{Dupont11}
\citation{Enge09cla}
\citation{cm}
\citation{BaHo62}
\newlabel{conj:bh}{{1}{4}{Bateman-Horn \cite {BaHo62}}{theorem.1}{}}
\newlabel{th:addseq}{{2}{4}{}{theorem.2}{}}
\citation{DoLi80}
\newlabel{th:bsgs}{{3}{5}{}{theorem.3}{}}
\citation{PaSt73}
\citation{ChCh88}
\citation{Bernstein2008}
\citation{Smith1989}
\citation{Johansson14}
\@writefile{toc}{\contentsline {section}{\numberline {2}Power series and addition sequences}{6}{section.2}}
\newlabel{sec:power}{{2}{6}{Power series and addition sequences}{section.2}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Dense exponent sequences}{6}{subsection.2.1}}
\newlabel{eq:bsgsformula}{{5}{6}{Dense exponent sequences}{equation.2.5}{}}
\citation{CoFrAvDoLaNgVe06}
\citation{DoLeSe81}
\citation{Knuth98}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2}Sparse exponent sequences and addition sequences}{7}{subsection.2.2}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {1}{\ignorespaces Short addition sequence}}{7}{algorithm.1}}
\newlabel{alg:addseq}{{1}{7}{Sparse exponent sequences and addition sequences}{algorithm.1}{}}
\citation{Cohen00}
\citation{DoLi80}
\@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces  Construction of the classical addition sequences for squares, trigonal numbers, and pentagonal numbers via finite differences.}}{8}{table.1}}
\newlabel{tab:classical}{{1}{8}{Construction of the classical addition sequences for squares, trigonal numbers, and pentagonal numbers via finite differences}{table.1}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.3}Cost of an addition sequence}{8}{subsection.2.3}}
\@writefile{lot}{\contentsline {table}{\numberline {2}{\ignorespaces  Costs associated with evaluating complex series using addition sequences.}}{9}{table.2}}
\newlabel{tab:cost}{{2}{9}{Costs associated with evaluating complex series using addition sequences}{table.2}{}}
\@writefile{toc}{\contentsline {section}{\numberline {3}Addition sequences for the Dedekind eta function}{9}{section.3}}
\newlabel{sec:eta}{{3}{9}{Addition sequences for the Dedekind eta function}{section.3}{}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {2}{\ignorespaces Dedekind eta function using optimized addition sequence}}{10}{algorithm.2}}
\newlabel{alg:eta}{{2}{10}{Addition sequences for the Dedekind eta function}{algorithm.2}{}}
\newlabel{lm:penta}{{4}{10}{}{theorem.4}{}}
\newlabel{eq:sigmadef}{{6}{10}{}{equation.3.6}{}}
\citation{Hirschhorn09}
\citation{Euler61}
\citation{Euler55}
\citation{Dickson23}
\citation{Euler61}
\@writefile{lot}{\contentsline {table}{\numberline {3}{\ignorespaces  Generalized pentagonal numbers}}{11}{table.3}}
\newlabel{tab:gpn}{{3}{11}{Generalized pentagonal numbers}{table.3}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1}One squaring and one multiplication}{11}{subsection.3.1}}
\newlabel{th:etatwoaplusb}{{5}{11}{}{theorem.5}{}}
\newlabel{lm:eight}{{6}{11}{}{theorem.6}{}}
\citation{Cox89}
\newlabel{eq:eight}{{7}{12}{One squaring and one multiplication}{equation.3.7}{}}
\citation{parigp}
\newlabel{prop:powersofthree}{{7}{13}{}{theorem.7}{}}
\newlabel{eq:normsqrtthree}{{8}{13}{One squaring and one multiplication}{equation.3.8}{}}
\newlabel{eq:normconductornine}{{9}{13}{One squaring and one multiplication}{equation.3.9}{}}
\citation{Euler58}
\citation{Euler60}
\citation{Euler58}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.2}One multiplication}{14}{subsection.3.2}}
\newlabel{lm:four}{{8}{14}{}{theorem.8}{}}
\newlabel{th:etaaplusb}{{9}{14}{}{theorem.9}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.3}One squaring}{15}{subsection.3.3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.4}One cube}{15}{subsection.3.4}}
\@writefile{toc}{\contentsline {section}{\numberline {4}Addition sequences for $\vartheta $-functions}{15}{section.4}}
\newlabel{sec:theta}{{4}{15}{Addition sequences for \texorpdfstring {$\theta $}{theta}-functions}{section.4}{}}
\citation{Legendre97}
\citation{Gauss01}
\citation{Grosswald85}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.1}Trigonal numbers and $\vartheta _2$}{16}{subsection.4.1}}
\newlabel{ssec:thetatwo}{{4.1}{16}{Trigonal numbers and \texorpdfstring {$\theta _2$}{theta2}}{subsection.4.1}{}}
\newlabel{th:thetatwo}{{10}{16}{}{theorem.10}{}}
\newlabel{th:thetatwothree}{{11}{16}{}{theorem.11}{}}
\citation{DoLi80}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.2}Squares and $\vartheta _0$ and $\vartheta _1$}{17}{subsection.4.2}}
\newlabel{ssec:thetazero}{{4.2}{17}{Squares and \texorpdfstring {$\theta _0$}{theta0} and \texorpdfstring {$\theta _1$}{theta1}}{subsection.4.2}{}}
\newlabel{th:thetazero}{{12}{17}{}{theorem.12}{}}
\newlabel{th:thetazerothree}{{13}{18}{}{theorem.13}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.3}Computing $\vartheta $ functions simultaneously}{18}{subsection.4.3}}
\newlabel{th:thetatwoaplusb}{{14}{18}{}{theorem.14}{}}
\newlabel{th:thetaaplusb}{{15}{19}{}{theorem.15}{}}
\@writefile{toc}{\contentsline {section}{\numberline {5}Baby-step giant-step algorithm}{20}{section.5}}
\newlabel{sec:bsgs}{{5}{20}{Baby-step giant-step algorithm}{section.5}{}}
\newlabel{eq:bsgscost}{{11}{20}{Baby-step giant-step algorithm}{equation.5.11}{}}
\newlabel{eq:bsgscost2}{{12}{20}{Baby-step giant-step algorithm}{equation.5.12}{}}
\citation{Gauss01}
\citation{Gauss01}
\citation{Gauss01}
\newlabel{eq:bsgscost3}{{13}{21}{Baby-step giant-step algorithm}{equation.5.13}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.1}Modular values of quadratic polynomials}{21}{subsection.5.1}}
\newlabel{ssec:modval}{{5.1}{21}{Modular values of quadratic polynomials}{subsection.5.1}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.1.1}Squares}{21}{subsubsection.5.1.1}}
\newlabel{eq:squares}{{14}{21}{Squares}{equation.5.14}{}}
\citation{RoSc62}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.1.2}Trigonal numbers}{22}{subsubsection.5.1.2}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.1.3}Generalized pentagonal numbers}{22}{subsubsection.5.1.3}}
\@writefile{lot}{\contentsline {table}{\numberline {4}{\ignorespaces  Successive minima of $s (m) / m$ for squares.}}{23}{table.4}}
\newlabel{tab:squaresminima}{{4}{23}{Successive minima of $s (m) / m$ for squares}{table.4}{}}
\@writefile{lot}{\contentsline {table}{\numberline {5}{\ignorespaces  Successive minima of $t (m) / m$ for trigonal numbers.}}{24}{table.5}}
\newlabel{tab:trigonalsminima}{{5}{24}{Successive minima of $t (m) / m$ for trigonal numbers}{table.5}{}}
\@writefile{lot}{\contentsline {table}{\numberline {6}{\ignorespaces  Successive minima of $p (m) / m$ for pentagonal numbers.}}{25}{table.6}}
\newlabel{tab:pentagonalsminima}{{6}{25}{Successive minima of $p (m) / m$ for pentagonal numbers}{table.6}{}}
\newlabel{lm:analytic}{{16}{26}{}{theorem.16}{}}
\newlabel{eq:limit}{{15}{26}{Generalized pentagonal numbers}{equation.5.15}{}}
\newlabel{th:quadpolym}{{17}{26}{}{theorem.17}{}}
\newlabel{eq:babygiantsteps}{{16}{26}{Generalized pentagonal numbers}{equation.5.16}{}}
\citation{RoSc62}
\citation{RoSc62}
\newlabel{eq:mpk}{{17}{27}{Generalized pentagonal numbers}{equation.5.17}{}}
\newlabel{eq:rstheta}{{18}{27}{Generalized pentagonal numbers}{equation.5.18}{}}
\newlabel{eq:pk}{{19}{27}{Generalized pentagonal numbers}{equation.5.19}{}}
\newlabel{eq:thetapk}{{20}{27}{Generalized pentagonal numbers}{equation.5.20}{}}
\citation{Arb}
\citation{cm}
\citation{mpir}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.2}Implementation}{28}{subsection.5.2}}
\@writefile{toc}{\contentsline {section}{\numberline {6}Benchmarks}{28}{section.6}}
\newlabel{sec:bench}{{6}{28}{Benchmarks}{section.6}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces Normalized theoretical cost in the FFT model ($(3m + 2.333s) / (3N)$ for $m$ complex multiplications and $s$ complex squarings) to add the first $N$ nonzero terms in the $q$-series of the Dedekind eta function, using three different addition sequences (AS) or the baby-step giant-step algorithm (BSGS). The classical addition sequences approaches\nobreakspace  {}$2$ multiplications per term. The short addition sequences generated with Algorithm\nobreakspace  {}\ref  {alg:addseq} and Algorithm\nobreakspace  {}\ref  {alg:eta} both approach\nobreakspace  {}$1$ multiplication per term. BSGS is asymptotically better than any addition sequence.}}{29}{figure.1}}
\newlabel{fig:etaefficiency}{{1}{29}{Normalized theoretical cost in the FFT model ($(3m + 2.333s) / (3N)$ for $m$ complex multiplications and $s$ complex squarings) to add the first $N$ nonzero terms in the $q$-series of the Dedekind eta function, using three different addition sequences (AS) or the baby-step giant-step algorithm (BSGS). The classical addition sequences approaches~$2$ multiplications per term. The short addition sequences generated with Algorithm~\ref {alg:addseq} and Algorithm~\ref {alg:eta} both approach~$1$ multiplication per term. BSGS is asymptotically better than any addition sequence}{figure.1}{}}
\citation{parigp}
\citation{cm}
\citation{Dupont11}
\@writefile{lot}{\contentsline {table}{\numberline {7}{\ignorespaces  Timings for computing the Dedekind eta function at different precisions. From left to right: bit precision, truncation order $T$ (last included exponent), seconds to compute $q = \qopname  \relax o{exp}(2 \pi i \tau )$, seconds to evaluate the sum using (AS), seconds to evaluate the sum using (BSGS), measured speed-up AS / BSGS, and theoretical speed-up based on counting multiplications in the FFT cost model.}}{30}{table.7}}
\newlabel{tab:timeeta}{{7}{30}{Timings for computing the Dedekind eta function at different precisions. From left to right: bit precision, truncation order $T$ (last included exponent), seconds to compute $q = \exp (2 \pi i \tau )$, seconds to evaluate the sum using (AS), seconds to evaluate the sum using (BSGS), measured speed-up AS / BSGS, and theoretical speed-up based on counting multiplications in the FFT cost model}{table.7}{}}
\@writefile{lot}{\contentsline {table}{\numberline {8}{\ignorespaces  Time in seconds to compute the theta functions $\vartheta _0(\tau ), \vartheta _1(\tau ), \vartheta _2(\tau )$ simultaneously, given $q = e^{\pi i \tau }$. Timings to compute the complex exponential are the same as in Table\nobreakspace  {}\ref  {tab:timeeta} and thus omitted.}}{30}{table.8}}
\newlabel{tab:timethetasimul}{{8}{30}{Time in seconds to compute the theta functions $\theta _0(\tau ), \theta _1(\tau ), \theta _2(\tau )$ simultaneously, given $q = e^{\pi i \tau }$. Timings to compute the complex exponential are the same as in Table~\ref {tab:timeeta} and thus omitted}{table.8}{}}
\bibstyle{jis}
\bibdata{enge1}
\bibcite{BaHo62}{1}
\@writefile{lot}{\contentsline {table}{\numberline {9}{\ignorespaces  Time in seconds to compute $\vartheta _0(\tau )$ alone, given $q = e^{\pi i \tau }$. Timings to compute the complex exponential are the same as in Table\nobreakspace  {}\ref  {tab:timeeta} and thus omitted.}}{31}{table.9}}
\newlabel{tab:timethetasingle}{{9}{31}{Time in seconds to compute $\theta _0(\tau )$ alone, given $q = e^{\pi i \tau }$. Timings to compute the complex exponential are the same as in Table~\ref {tab:timeeta} and thus omitted}{table.9}{}}
\@writefile{lot}{\contentsline {table}{\numberline {10}{\ignorespaces  Time in seconds to compute $\eta (\tau )$.}}{31}{table.10}}
\newlabel{tab:timecomparison}{{10}{31}{Time in seconds to compute $\eta (\tau )$}{table.10}{}}
\@writefile{toc}{\contentsline {section}{\numberline {7}Acknowledgments}{31}{section.7}}
\bibcite{parigp}{2}
\bibcite{Bernstein2008}{3}
\bibcite{ChCh88}{4}
\bibcite{Cohen00}{5}
\bibcite{CoFrAvDoLaNgVe06}{6}
\bibcite{Cox89}{7}
\bibcite{Dickson23}{8}
\bibcite{DoLi80}{9}
\bibcite{DoLeSe81}{10}
\bibcite{Dupont11}{11}
\bibcite{Enge09cla}{12}
\bibcite{Enge09mod}{13}
\bibcite{cm}{14}
\bibcite{EnMo14}{15}
\bibcite{EnSc04}{16}
\bibcite{EnSc13}{17}
\bibcite{Euler55}{18}
\bibcite{Euler58}{19}
\bibcite{Euler60}{20}
\bibcite{Euler61}{21}
\bibcite{Euler83}{22}
\bibcite{Gauss01}{23}
\bibcite{Grosswald85}{24}
\bibcite{mpir}{25}
\bibcite{Hirschhorn09}{26}
\bibcite{Johansson14}{27}
\bibcite{Arb}{28}
\bibcite{Knuth98}{29}
\bibcite{Legendre97}{30}
\bibcite{Mumford83}{31}
\bibcite{Mumford84}{32}
\bibcite{Mumford91}{33}
\bibcite{PaSt73}{34}
\bibcite{Rademacher38}{35}
\bibcite{RoSc62}{36}
\bibcite{Schertz02}{37}
\bibcite{Smith1989}{38}
\bibcite{Weber08}{39}