More Like this

1. An algorithm and computation to verify Legendre’s conjecture up to $$7\cdot 10^{13}$$

   https://doi.org/10.1007/s40993-024-00589-4  

   Sorenson, Jonathan; Webster, Jonathan (March 2025, Research in Number Theory)

   Abstract We state a general purpose algorithm for quickly finding primes in evenly divided sub-intervals. Legendre’s conjecture claims that for every positive integern, there exists a prime between$$n^2$$ $n^2$and$$(n+1)^2$$ ${(n+1)}^2$. Oppermann’s conjecture subsumes Legendre’s conjecture by claiming there are primes between$$n^2$$ $n^2$and$$n(n+1)$$ $n(n+1)$and also between$$n(n+1)$$ $n(n+1)$and$$(n+1)^2$$ ${(n+1)}^2$. Using Cramér’s conjecture as the basis for a heuristic run-time analysis, we show that our algorithm can verify Oppermann’s conjecture, and hence also Legendre’s conjecture, for all$$n\le N$$ $n\le N$in time$$O( N \log N \log \log N)$$ $O(NlogNloglogN)$and space$$N^{O(1/\log \log N)}$$ $N^{O(1/loglogN)}$. We implemented a parallel version of our algorithm and improved the empirical verification of Oppermann’s conjecture from the previous$$N = 2\cdot 10^{9}$$ $N=2·{10}^9$up to$$N = 7.05\cdot 10^{13} > 2^{46}$$ $N=7.05·{10}^{13}>2^{46}$, so we were finding 27 digit primes. The computation ran for about half a year on each of two platforms: four Intel Xeon Phi 7210 processors using a total of 256 cores, and a 192-core cluster of Intel Xeon E5-2630 2.3GHz processors. 

   more » « less
2. Spherical convex hull of random points on a wedge

   https://doi.org/10.1007/s00208-023-02704-9  

   Besau, Florian; Gusakova, Anna; Reitzner, Matthias; Schütt, Carsten; Thäle, Christoph; Werner, Elisabeth_M (August 2023, Mathematische Annalen)

   Abstract Consider two half-spaces$$H_1^+$$ $H_1^{+}$and$$H_2^+$$ $H_2^{+}$in$${\mathbb {R}}^{d+1}$$ $R^{d+1}$whose bounding hyperplanes$$H_1$$ $H_1$and$$H_2$$ $H_2$are orthogonal and pass through the origin. The intersection$${\mathbb {S}}_{2,+}^d:={\mathbb {S}}^d\cap H_1^+\cap H_2^+$$ $S_{2,+}^d:=S^d\cap H_1^{+}\cap H_2^{+}$is a spherical convex subset of thed-dimensional unit sphere$${\mathbb {S}}^d$$ $S^d$, which contains a great subsphere of dimension$$d-2$$ $d-2$and is called a spherical wedge. Choosenindependent random points uniformly at random on$${\mathbb {S}}_{2,+}^d$$ $S_{2,+}^d$and consider the expected facet number of the spherical convex hull of these points. It is shown that, up to terms of lower order, this expectation grows like a constant multiple of$$\log n$$ $logn$. A similar behaviour is obtained for the expected facet number of a homogeneous Poisson point process on$${\mathbb {S}}_{2,+}^d$$ $S_{2,+}^d$. The result is compared to the corresponding behaviour of classical Euclidean random polytopes and of spherical random polytopes on a half-sphere. 

   more » « less
3. Dimension-free discretizations of the uniform norm by small product sets

   https://doi.org/10.1007/s00222-024-01306-9  

   Becker, Lars; Klein, Ohad; Slote, Joseph; Volberg, Alexander; Zhang, Haonan (December 2024, Inventiones mathematicae)

   Abstract Let$$f$$ $f$be an analytic polynomial of degree at most$$K-1$$ $K-1$. A classical inequality of Bernstein compares the supremum norm of$$f$$ $f$over the unit circle to its supremum norm over the sampling set of the$$K$$ $K$-th roots of unity. Many extensions of this inequality exist, often understood under the umbrella of Marcinkiewicz–Zygmund-type inequalities for$$L^{p},1\le p\leq \infty $$ $L^p,1\le p\le \infty$norms. We study dimension-free extensions of these discretization inequalities in the high-dimension regime, where existing results construct sampling sets with cardinality growing with the total degree of the polynomial. In this work we show that dimension-free discretizations are possible with sampling sets whose cardinality is independent of$$\deg (f)$$ $deg\left(f\right)$and is instead governed by the maximumindividualdegree of$$f$$ $f$;i.e., the largest degree of$$f$$ $f$when viewed as a univariate polynomial in any coordinate. For example, we find that for$$n$$ $n$-variate analytic polynomials$$f$$ $f$of degree at most$$d$$ $d$and individual degree at most$$K-1$$ $K-1$,$$\|f\|_{L^{\infty }(\mathbf{D}^{n})}\leq C(X)^{d}\|f\|_{L^{\infty }(X^{n})}$$ ${\parallel f\parallel }_{L^{\infty }\left(D^n\right)}\le C{\left(X\right)}^d{\parallel f\parallel }_{L^{\infty }\left(X^n\right)}$for any fixed$$X$$ $X$in the unit disc$$\mathbf{D}$$ $D$with$$|X|=K$$ $\left|X\right|=K$. The dependence on$$d$$ $d$in the constant is tight for such small sampling sets, which arise naturally for example when studying polynomials of bounded degree coming from functions on products of cyclic groups. As an application we obtain a proof of the cyclic group Bohnenblust–Hille inequality with an explicit constant$$\mathcal{O}(\log K)^{2d}$$ $O{(logK)}^{2d}$. 

   more » « less
4. An Efficient ZK Compiler from SIMD Circuits to General Circuits

   https://doi.org/10.1007/s00145-024-09531-4  

   Bui, Dung; Chu, Haotian; Couteau, Geoffroy; Wang, Xiao; Weng, Chenkai; Yang, Kang; Yu, Yu (January 2025, Journal of Cryptology)

   Abstract We propose a generic compiler that can convert any zero-knowledge (ZK) proof for SIMD circuits to general circuits efficiently, and an extension that can preserve the space complexity of the proof systems. Our compiler can immediately produce new results improving upon state of the art.By plugging in our compiler to Antman, an interactive sublinear-communication protocol, we improve the overall communication complexity for general circuits from$$\mathcal {O}(C^{3/4})$$ $O\left(C^{3/4}\right)$to$$\mathcal {O}(C^{1/2})$$ $O\left(C^{1/2}\right)$. Our implementation shows that for a circuit of size$$2^{27}$$ $2^{27}$, it achieves up to$$83.6\times $$ $83.6\times$improvement on communication compared to the state-of-the-art implementation. Its end-to-end running time is at least$$70\%$$ $70\%$faster in a 10Mbps network.Using the recent results on compressed$$\varSigma $$ $\Sigma$-protocol theory, we obtain a discrete-log-based constant-round zero-knowledge argument with$$\mathcal {O}(C^{1/2})$$ $O\left(C^{1/2}\right)$communication and common random string length, improving over the state of the art that has linear-size common random string and requires heavier computation.We improve the communication of a designatedn-verifier zero-knowledge proof from$$\mathcal {O}(nC/B+n^2B^2)$$ $O(nC/B+n^2{B}^2)$to$$\mathcal {O}(nC/B+n^2)$$ $O(nC/B+n^2)$.To demonstrate the scalability of our compilers, we were able to extract a commit-and-prove SIMD ZK from Ligero and cast it in our framework. We also give one instantiation derived from LegoSNARK, demonstrating that the idea of CP-SNARK also fits in our methodology. 

   more » « less
5. Stochastic dual dynamic programming for multistage stochastic mixed-integer nonlinear optimization

   https://doi.org/10.1007/s10107-022-01875-8  

   Zhang, Shixuan; Sun, Xu Andy (August 2022, Mathematical Programming)

   Abstract In this paper, we study multistage stochastic mixed-integer nonlinear programs (MS-MINLP). This general class of problems encompasses, as important special cases, multistage stochastic convex optimization withnon-Lipschitzianvalue functions and multistage stochastic mixed-integer linear optimization. We develop stochastic dual dynamic programming (SDDP) type algorithms with nested decomposition, deterministic sampling, and stochastic sampling. The key ingredient is a new type of cuts based on generalized conjugacy. Several interesting classes of MS-MINLP are identified, where the new algorithms are guaranteed to obtain the global optimum without the assumption of complete recourse. This significantly generalizes the classic SDDP algorithms. We also characterize the iteration complexity of the proposed algorithms. In particular, for a$$(T+1)$$ $(T+1)$-stage stochastic MINLP satisfyingL-exact Lipschitz regularization withd-dimensional state spaces, to obtain an$$\varepsilon $$ $\epsilon$-optimal root node solution, we prove that the number of iterations of the proposed deterministic sampling algorithm is upper bounded by$${\mathcal {O}}((\frac{2LT}{\varepsilon })^d)$$ $O\left({\left(\frac{2LT}{\epsilon }\right)}^d\right)$, and is lower bounded by$${\mathcal {O}}((\frac{LT}{4\varepsilon })^d)$$ $O\left({\left(\frac{\mathrm{LT}}{4\epsilon }\right)}^d\right)$for the general case or by$${\mathcal {O}}((\frac{LT}{8\varepsilon })^{d/2-1})$$ $O\left({\left(\frac{\mathrm{LT}}{8\epsilon }\right)}^{d/2-1}\right)$for the convex case. This shows that the obtained complexity bounds are rather sharp. It also reveals that the iteration complexity dependspolynomiallyon the number of stages. We further show that the iteration complexity dependslinearlyonT, if all the state spaces are finite sets, or if we seek a$$(T\varepsilon )$$ $\left(T\epsilon \right)$-optimal solution when the state spaces are infinite sets, i.e. allowing the optimality gap to scale withT. To the best of our knowledge, this is the first work that reports global optimization algorithms as well as iteration complexity results for solving such a large class of multistage stochastic programs. The iteration complexity study resolves a conjecture by the late Prof. Shabbir Ahmed in the general setting of multistage stochastic mixed-integer optimization. 

   more » « less