### Top 10 Arxiv Papers Today in Symbolic Computation

##### #1. Incrementally and inductively constructing basis of multiplicative dependence lattice of non-zero algebraic numbers
###### Tao Zheng
Let $x=(x_1,x_2,\cdots,x_n)^T$ be a vector of non-zero algebraic numbers, the set $\mathcal{R}_x:=\{(k_1,k_2,\cdots,k_n)^T\in\mathbb{Z}^n\;|\;x_1^{k_1}x_2^{k_2}\cdots x_n^{k_n}=1\}$ is called \emph{the multiplicative dependence lattice} of $x$. This paper develops an efficient incremental algorithm to compute a basis of $\mathcal{R}_x$. This algorithm constructs inductively a basis of the lattice as the dimension increases. This is the very first algorithm for computing the basis of the lattice, although a lot of efforts have been made to understand this lattice. In this paper we propose the conception of the \emph{rank} of a finite sequence of non-zero algebraic numbers, which turns out to be closely related to the rank of the lattice, and as well as to the complexity. The complexity of the algorithm depends not mainly on the dimension $n$ but on the rank of the sequence $x_1,x_2,\cdots,x_n$, which can be much smaller than $n$.
more | pdf | html
None.
###### Tweets
ComputerPapers: Incrementally and inductively constructing basis of multiplicative dependence lattice of non-zero algebraic numbers. https://t.co/ykwWyHXgl6
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 8889
Unqiue Words: 1817

##### #2. Fast transforms over finite fields of characteristic two
###### Nicholas Coxon
An additive fast Fourier transform over a finite field of characteristic two efficiently evaluates polynomials at every element of an $\mathbb{F}_2$-linear subspace of the field. We view these transforms as performing a change of basis from the monomial basis to the associated Lagrange basis, and consider the problem of performing the various conversions between these two bases, the associated Newton basis, and the '' novel '' basis of Lin, Chung and Han (FOCS 2014). Existing algorithms are divided between two families, those designed for arbitrary subspaces and more efficient algorithms designed for specially constructed subspaces of fields with degree equal to a power of two. We generalise techniques from both families to provide new conversion algorithms that may be applied to arbitrary subspaces, but which benefit equally from the specially constructed subspaces. We then construct subspaces of fields with smooth degree for which our algorithms provide better performance than existing algorithms.
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 27382
Unqiue Words: 2924

##### #3. What Can (and Can't) we Do with Sparse Polynomials?
###### Daniel S. Roche
Simply put, a sparse polynomial is one whose zero coefficients are not explicitly stored. Such objects are ubiquitous in exact computing, and so naturally we would like to have efficient algorithms to handle them. However, with this compact storage comes new algorithmic challenges, as fast algorithms for dense polynomials may no longer be efficient. In this tutorial we examine the state of the art for sparse polynomial algorithms in three areas: arithmetic, interpolation, and factorization. The aim is to highlight recent progress both in theory and in practice, as well as opportunities for future work.
more | pdf | html
None.
###### Tweets
ComputerPapers: What Can (and Can't) we Do with Sparse Polynomials?. https://t.co/0ym0V6FQUB
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 6676
Unqiue Words: 2184

##### #4. Aligator.jl - A Julia Package for Loop Invariant Generation
###### Andreas Humenberger, Maximilian Jaroschek, Laura Kovács
We describe the Aligator.jl software package for automatically generating all polynomial invariants of the rich class of extended P-solvable loops with nested conditionals. Aligator.jl is written in the programming language Julia and is open-source. Aligator.jl transforms program loops into a system of algebraic recurrences and implements techniques from symbolic computation to solve recurrences, derive closed form solutions of loop variables and infer the ideal of polynomial invariants by variable elimination based on Gr\"obner basis computation.
more | pdf | html
None.
###### Tweets
M157q_News_RSS: Aligator.jl - A Julia Package for Loop Invariant Generation. (arXiv:1808.05394v1 [https://t.co/LljFWnr6hA]) https://t.co/Q30DI64HsF We describe the Aligator.j
###### Github

Aligator is a Mathematica software package for generating loop invariants.

Repository: aligator
User: ahumenberger
Language: Mathematica
Stargazers: 0
Subscribers: 4
Forks: 0
Open Issues: 0
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 2245
Unqiue Words: 941

##### #5. Computer algebra tools for Feynman integrals and related multi-sums
###### Johannes Blümlein, Carsten Schneider
In perturbative calculations, e.g., in the setting of Quantum Chromodynamics (QCD) one aims at the evaluation of Feynman integrals. Here one is often faced with the problem to simplify multiple nested integrals or sums to expressions in terms of indefinite nested integrals or sums. Furthermore, one seeks for solutions of coupled systems of linear differential equations, that can be represented in terms of indefinite nested sums (or integrals). In this article we elaborate the main tools and the corresponding packages, that we have developed and intensively used within the last 10 years in the course of our QCD-calculations.
more | pdf | html
###### Tweets
MathPHYPapers: Computer algebra tools for Feynman integrals and related multi-sums. https://t.co/rjdkpANStx
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 7508
Unqiue Words: 1988

##### #6. Proceedings of the 15th International Workshop on the ACL2 Theorem Prover and Its Applications
###### Shilpi Goel, Matt Kaufmann
This volume contains the proceedings of the Fifteenth International Workshop on the ACL2 Theorem Prover and Its Applications (ACL2-2018), a two-day workshop held in Austin, Texas, USA, on November 5-6, 2018, immediately after FMCAD'18. The proceedings of ACL2-2018 include eleven long papers and two extended abstracts.
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

##### #7. Bohemian Upper Hessenberg Matrices
###### Eunice Y. S. Chan, Robert M. Corless, Laureano Gonzalez-Vega, J. Rafael Sendra, Juana Sendra, Steven E. Thornton
We look at Bohemian matrices, specifically those with entries from $\{-1, 0, {+1}\}$. More, we specialize the matrices to be upper Hessenberg, with subdiagonal entries $\pm1$. Many properties remain after these specializations, some of which surprised us. We find two recursive formulae for the characteristic polynomials of upper Hessenberg matrices. Focusing on only those matrices whose characteristic polynomials have maximal height allows us to explicitly identify these polynomials and give a lower bound on their height. This bound is exponential in the order of the matrix. We count stable matrices, normal matrices, and neutral matrices, and tabulate the results of our experiments. We prove a theorem about the only possible kinds of normal matrices amongst a specific family of Bohemian upper Hessenberg matrices.
more | pdf | html
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 6
Total Words: 7998
Unqiue Words: 2076

##### #8. Toward an Optimal Quantum Algorithm for Polynomial Factorization over Finite Fields
We present a randomized quantum algorithm for polynomial factorization over finite fields. For polynomials of degree $n$ over a finite field $\F_q$, the average-case complexity of our algorithm is an expected $O(n^{1 + o(1)} \log^{2 + o(1)}q)$ bit operations. Only for a negligible subset of polynomials of degree $n$ our algorithm has a higher complexity of $O(n^{4 / 3 + o(1)} \log^{2 + o(1)}q)$ bit operations. This breaks the classical $3/2$-exponent barrier for polynomial factorization over finite fields \cite{guo2016alg}.
more | pdf | html
None.
###### Tweets
enclanglement: A quantum algorithm for factoring polynomials (for some reason, not posted under quant-ph). https://t.co/pxMFlBJzux
MathPaper: Toward an Optimal Quantum Algorithm for Polynomial Factorization over Finite Fields. https://t.co/DoCDEdMpj9
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 6430
Unqiue Words: 1451

##### #9. Computing Elimination Ideals and Discriminants of Likelihood Equations
###### Xiaoxian Tang, Timo De Wolff, Rukai Zhao
We develop a probabilistic algorithm for computing elimination ideals of likelihood equations, which is for larger models by far more efficient than directly computing Groebner bases or the interpolation method proposed in the first author's previous work. The efficiency is improved by a theoretical result showing that the sum of data variables appears in most coefficients of the generator polynomial of elimination ideal. Furthermore, applying the known structures of Newton polytopes of discriminants, we can also efficiently deduce discriminants of the elimination ideals. For instance, the discriminants of 3 by 3 matrix model and one Jukes-Cantor model in phylogenetics (with sizes over 30 GB and 8 GB text files, respectively) can be computed by our methods.
more | pdf | html
None.
###### Tweets
StatsPapers: Computing Elimination Ideals and Discriminants of Likelihood Equations. https://t.co/4dC06cDFOa
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 17165
Unqiue Words: 3179

##### #10. Towards a symbolic summation theory for unspecified sequences
###### Peter Paule, Carsten Schneider
The article addresses the problem whether indefinite double sums involving a generic sequence can be simplified in terms of indefinite single sums. Depending on the structure of the double sum, the proposed summation machinery may provide such a simplification without exceptions. If it fails, it may suggest a more advanced simplification introducing in addition a single nested sum where the summand has to satisfy a particular constraint. More precisely, an explicitly given parameterized telescoping equation must hold. Restricting to the case that the arising unspecified sequences are specialized to the class of indefinite nested sums defined over hypergeometric, multi-basic or mixed hypergeometric products, it can be shown that this constraint is not only sufficient but also necessary.
more | pdf | html
None.
###### Tweets
MathPaper: Towards a symbolic summation theory for unspecified sequences. https://t.co/UwwFmJn0JY
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 16226
Unqiue Words: 2796

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

Tracking 57,756 papers.

###### Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Online
###### Stats
Tracking 57,756 papers.