Let ${mathcal D}(n)$ be the maximal determinant for $n times n$ ${pm 1}$-matrices, and $mathcal R(n) = {mathcal D}(n)/n^{n/2}$ be the ratio of ${mathcal D}(n)$ to the Hadamard upper bound. Using the probabilistic method, we prove new lower bounds on ${mathcal D}(n)$ and $mathcal R(n)$ in terms of $d = n-h$, where $h$ is the order of a Hadamard matrix and $h$ is maximal subject to $h le n$. For example, $mathcal R(n) > (pi e/2)^{-d/2}$ if $1 le d le 3$, and $mathcal R(n) > (pi e/2)^{-d/2}(1 - d^2(pi/(2h))^{1/2})$ if $d > 3$. By a recent result of Livinskyi, $d^2/h^{1/2} to 0$ as $n to infty$, so the second bound is close to $(pi e/2)^{-d/2}$ for large $n$. Previous lower bounds tended to zero as $n to infty$ with $d$ fixed, except in the cases $d in {0,1}$. For $d ge 2$, our bounds are better for all sufficiently large $n$. If the Hadamard conjecture is true, then $d le 3$, so the first bound above shows that $mathcal R(n)$ is bounded below by a positive constant $(pi e/2)^{-3/2} > 0.1133$.
We consider several families of binomial sum identities whose definition involves the absolute value function. In particular, we consider centered double sums of the form [S_{alpha,beta}(n) := sum_{k,;ell}binom{2n}{n+k}binom{2n}{n+ell} |k^alpha-ell^alpha|^beta,] obtaining new results in the cases $alpha = 1, 2$. We show that there is a close connection between these double sums in the case $alpha=1$ and the single centered binomial sums considered by Tuenter.
Let $D(n)$ be the maximal determinant for $n times n$ ${pm 1}$-matrices, and ${mathcal R}(n) = D(n)/n^{n/2}$ be the ratio of $D(n)$ to the Hadamard upper bound. We give several new lower bounds on ${mathcal R}(n)$ in terms of $d$, where $n = h+d$, $h$ is the order of a Hadamard matrix, and $h$ is maximal subject to $h le n$. A relatively simple bound is [{mathcal R}(n) ge left(frac{2}{pi e}right)^{d/2} left(1 - d^2left(frac{pi}{2h}right)^{1/2}right) ;text{ for all }; n ge 1.] An asymptotically sharper bound is [{mathcal R}(n) ge left(frac{2}{pi e}right)^{d/2} expleft(dleft(frac{pi}{2h}right)^{1/2} + ; Oleft(frac{d^{5/3}}{h^{2/3}}right)right).] We also show that [{mathcal R}(n) ge left(frac{2}{pi e}right)^{d/2}] if $n ge n_0$ and $n_0$ is sufficiently large, the threshold $n_0$ being independent of $d$, or for all $nge 1$ if $0 le d le 3$ (which would follow from the Hadamard conjecture). The proofs depend on the probabilistic method, and generalise previous results that were restricted to the cases $d=0$ and $d=1$.
We give upper and lower bounds on the determinant of a perturbation of the identity matrix or, more generally, a perturbation of a nonsingular diagonal matrix. The matrices considered are, in general, diagonally dominant. The lower bounds are best possible, and in several cases they are stronger than well-known bounds due to Ostrowski and other authors. If $A = I-E$ is an $n times n$ matrix and the elements of $E$ are bounded in absolute value by $varepsilon le 1/n$, then a lower bound of Ostrowski (1938) is $det(A) ge 1-nvarepsilon$. We show that if, in addition, the diagonal elements of $E$ are zero, then a best-possible lower bound is [det(A) ge (1-(n-1)varepsilon),(1+varepsilon)^{n-1}.] Corresponding upper bounds are respectively [det(A) le (1 + 2varepsilon + nvarepsilon^2)^{n/2}] and [det(A) le (1 + (n-1)varepsilon^2)^{n/2}.] The first upper bound is stronger than Ostrowskis bound (for $varepsilon < 1/n$) $det(A) le (1 - nvarepsilon)^{-1}$. The second upper bound generalises Hadamards inequality, which is the case $varepsilon = 1$. A necessary and sufficient condition for our upper bounds to be best possible for matrices of order $n$ and all positive $varepsilon$ is the existence of a skew-Hadamard matrix of order $n$.
The general number field sieve (GNFS) is the most efficient algorithm known for factoring large integers. It consists of several stages, the first one being polynomial selection. The quality of the chosen polynomials in polynomial selection can be modelled in terms of size and root properties. In this paper, we describe some algorithms for selecting polynomials with very good root properties.
