More Like this

1. Singmaster’s Conjecture In The Interior Of Pascal’s Triangle

   https://doi.org/10.1093/qmath/haac006  

   Matomäki, Kaisa; Radziwiłł, Maksym; Shao, Xuancheng; Tao, Terence; Teräväinen, Joni (April 2022, The Quarterly Journal of Mathematics)

   Abstract Singmaster’s conjecture asserts that every natural number greater than one occurs at most a bounded number of times in Pascal’s triangle; that is, for any natural number $$t \geq 2$$, the number of solutions to the equation $$\binom{n}{m} = t$$ for natural numbers $$1 \leq m \lt n$$ is bounded. In this paper we establish this result in the interior region $$\exp(\log^{2/3+\varepsilon} n) \leq m \leq n - \exp(\log^{2/3+\varepsilon} n)$$ for any fixed ɛ > 0. Indeed, when t is sufficiently large depending on ɛ, we show that there are at most four solutions (or at most two in either half of Pascal’s triangle) in this region. We also establish analogous results for the equation $$(n)_m = t$$, where $$(n)_m := n(n-1) \dots (n-m+1)$$ denotes the falling factorial. 

   more » « less
2. Almost All Alternating Groups are Invariably Generated by Two Elements of Prime Order

   https://doi.org/10.1093/imrn/rnac354  

   Teräväinen, Joni (January 2023, International Mathematics Research Notices)

   Abstract We show that for all $$n\leq X$$ apart from $$O(X\exp (-c(\log X)^{1/2}(\log \log X)^{1/2}))$$ exceptions, the alternating group $$A_{n}$$ is invariably generated by two elements of prime order. This answers (in a quantitative form) a question of Guralnick, Shareshian, and Woodroofe. 

   more » « less
3. On lower bounds for Erdős-Szekeres products

   https://doi.org/10.1090/proc/15503  

   Billsborough, C.; Freedman, M.; Hart, S.; Kowalsky, G.; Lubinsky, D.; Pomeranz, A.; Sammel, A. (October 2021, Proceedings of the American Mathematical Society)

   Let { s j } j = 1 n \left \{ s_{j}\right \} _{j=1}^{n} be positive integers. We show that for any 1 ≤ L ≤ n , 1\leq L\leq n, ‖ ∏ j = 1 n ( 1 − z s j ) ‖ L ∞ ( | z | = 1 ) ≥ exp ⁡ ( 1 2 e L ( s 1 s 2 … s L ) 1 / L ) . \begin{equation*} \left \Vert \prod _{j=1}^{n}\left ( 1-z^{s_{j}}\right ) \right \Vert _{L_{\infty }\left ( \left \vert z\right \vert =1\right ) }\geq \exp \left ( \frac {1}{2e}\frac {L}{\left ( s_{1}s_{2}\ldots s_{L}\right ) ^{1/L}}\right ) . \end{equation*} In particular, this gives geometric growth if a positive proportion of the { s j } \left \{ s_{j}\right \} are bounded. We also show that when the { s j } \left \{ s_{j}\right \} grow regularly and faster than j ( log ⁡ j ) 2 + ε j\left ( \log j\right ) ^{2+\varepsilon } , some ε > 0 \varepsilon >0 , then the norms grow faster than exp ⁡ ( ( log ⁡ n ) 1 + δ ) \exp \left ( \left ( \log n\right ) ^{1+\delta }\right ) for some δ > 0 \delta >0 . 

   more » « less
4. Approximately Hadamard Matrices and Riesz Bases in Random Frames

   https://doi.org/10.1093/imrn/rnad080  

   Dong, Xiaoyu; Rudelson, Mark (April 2023, International Mathematics Research Notices)

   Abstract An $$n \times n$$ matrix with $$\pm 1$$ entries that acts on $${\mathbb {R}}^{n}$$ as a scaled isometry is called Hadamard. Such matrices exist in some, but not all dimensions. Combining number-theoretic and probabilistic tools, we construct matrices with $$\pm 1$$ entries that act as approximate scaled isometries in $${\mathbb {R}}^{n}$$ for all $$n \in {\mathbb {N}}$$. More precisely, the matrices we construct have condition numbers bounded by a constant independent of $$n$$. Using this construction, we establish a phase transition for the probability that a random frame contains a Riesz basis. Namely, we show that a random frame in $${\mathbb {R}}^{n}$$ formed by $$N$$ vectors with independent identically distributed coordinate having a nondegenerate symmetric distribution contains many Riesz bases with high probability provided that $$N \ge \exp (Cn)$$. On the other hand, we prove that if the entries are sub-Gaussian, then a random frame fails to contain a Riesz basis with probability close to $$1$$ whenever $$N \le \exp (cn)$$, where $c<C$ are constants depending on the distribution of the entries. 

   more » « less
5. Factoring using multiplicative relations modulo $$n$$: a subexponential algorithm inspired by the index calculus

   Stange, Katherine E (October 2023, Mathematical Cryptology)

   We demonstrate that a modification of the classical index calculus algorithm can be used to factor integers. More generally, we reduce the factoring problem to finding an overdetermined system of multiplicative relations in any factor base modulo $$n$$, where $$n$$ is the integer whose factorization is sought. The algorithm has subexponential runtime $$\exp(O(\sqrt{\log n \log \log n}))$$ (or $$\exp(O( (\log n)^{1/3} (\log \log n)^{2/3} ))$$ with the addition of a number field sieve), but requires a rational linear algebra phase, which is more intensive than the linear algebra phase of the classical index calculus algorithm. The algorithm is certainly slower than the best known factoring algorithms, but is perhaps somewhat notable for its simplicity and its similarity to the index calculus. 

   more » « less