Search

In this paper, we study the Cartesian product of signed graphs as defined by Germina, Hameed and Zaslavsky (2011). Here we focus on its algebraic properties and look at the chromatic number of some Cartesian products. One of our main results is the unicity of the prime factor decomposition of signed graphs. This leads us to present an algorithm to compute this decomposition in linear time based on a decomposition algorithm for oriented graphs by Imrich and Peterin (2018). We also study the chromatic number of a signed graph, that is the minimum order of a signed graph to which the input signed graph admits a homomorphism, of graphs with underlying graph of the form P n □ P m , of Cartesian products of signed paths, of Cartesian products of signed complete graphs and of Cartesian products of signed cycles.

Let p be a rational prime and q a power of p. Let n be a non-constant monic polynomial in F q [ t ] which has a prime factor of degree prime to q − 1 . In this paper, we define a Drinfeld modular curve Y 1 Δ ( n ) over A [ 1 / n ] and study the structure around cusps of its compactification X 1 Δ ( n ) , in a parallel way to Katz-Mazur's work on classical modular curves. Using them, we also define a Hodge bundle over X 1 Δ ( n ) such that Drinfeld modular forms of level Γ 1 ( n ) , weight k and some type are identified with global sections of its k-th tensor power.

Our initial problem is to represent classes $$m$$ modulo $$q$$ by a sum of three terms, two being taken from rather small sets $$\mathcal A$$ and $$\mathcal B$$ and the third one having an odd number of prime factors (the so-called irregular numbers in S. Ramanujan’s terminology) and lying in an interval $$[q^{20r},q^{20r}+q^{16r}]$$ for some given $$r\ge1$$ . We show that it is always possible to do so provided that $$|\mathcal A|\cdot|\mathcal B|\ge q(\log q)^2$$ . The proof leads us to study the trigonometric polynomials over irregular numbers in a short interval and to seek very sharp bounds for them. We prove in particular that $$\sum_{q^{20r}\le s \le q^{20r}+q^{16r}}e(sa/q)\ll q^{16r}(\log q)/\sqrt{\varphi(q)}$$ uniformly in $$r$$ , where $$s$$ ranges over the irregular numbers. We develop a technique initiated by Selberg and Motohashi to do so. In short, we express the characteristic function of the irregular numbers via a family of bilinear decompositions akin to Iwaniec’s amplification process, and that uses pseudo-characters or local models. The technique applies to the Liouville function, to the Mobius function and also to the von Mangoldt function, in which case it is slightly more difficult. It is however simple enough to warrant explicit estimates, and we prove, for instance, that $$\bigl|\sum_{X

Let $$D_n(x;a)$$ and $$E_n(x;a)\in {\mathbb {F}}_q[x]$$ be Dickson polynomials of first and second kind respectively, where $${\mathbb {F}}_q$$ is a finite field with q elements. In this article we show explicitly the irreducible factors of these polynomials in the case that every prime divisor of n divides $$q-1$$ . This result generalizes the results found in (Finite Fields Appl. 3:84–96, 1997; Explicit factorization of cyclotomic and Dickson polynomials over finite fields, Springer, Berlin, 2007; Finite Fields Appl. 38:40-56, 2016; Discrete Math. 342:111618, 2019).

Denote by P + ( n ) the largest prime factor of an integer n. In this paper, we show that the Elliott-Halberstam conjecture for friable integers (or smooth integers) implies three conjectures concerning the largest prime factors of consecutive integers, formulated by Erdős-Turan in the 1930s, by Erdős-Pomerance in 1978, and by Erdős in 1979 respectively. More precisely, assuming the Elliott-Halberstam conjecture for friable integers, we deduce that the three sets E 1 = { n ⩽ x : P + ( n ) ⩽ x s , P + ( n + 1 ) ⩽ x t } , E 2 = { n ⩽ x : P + ( n ) P + ( n + 1 ) x α } , E 3 = { n ⩽ x : P + ( n ) P + ( n + 1 ) } have an asymptotic density ρ ( 1 / s ) ρ ( 1 / t ) , ∫ T α u ( y ) u ( z ) d y d z , 1/2 respectively for s , t ∈ ( 0 , 1 ) , where ρ ( ⋅ ) is the Dickman function, and T α , u ( ⋅ ) are defined in Theorem 2.

After briefly describing the origin and the scope of the Turan–Kubilius inequality, we show how this important inequality leads to the law of large numbers for the prime factors belonging to the middle region of a random natural number. Finally, we show how the same idea is implemented for a sparser subset, the set of shifted primes.

Optimization algorithms play a central role in chemistry since optimization is the computational keystone of most molecular and electronic structure calculations. Herein, we introduce the iterative power algorithm (IPA) for global optimization and a formal proof of convergence for both discrete and continuous global search problems, which is essential for applications in chemistry such as molecular geometry optimization. IPA implements the power iteration method in quantics tensor train (QTT) representations. Analogous to the imaginary time propagation method with infinite mass, IPA starts with an initial probability distribution ρ0(x) and iteratively applies the recurrence relation ρk+1(x) = U(x) ρk(x)/∥Uρk∥L1, where U(x) = e-V(x) is defined in terms of the potential energy surface (PES) V(x) with global minimum at x = x*. Upon convergence, the probability distribution becomes a delta function δ(x - x*), so the global minimum can be obtained as the position expectation value x* = Tr[x δ(x - x*)]. QTT representations of V(x) and ρ(x) are generated by fast adaptive interpolation of multidimensional arrays to bypass the curse of dimensionality and the need to evaluate V(x) for all possible values of x. We illustrate the capabilities of IPA for global search optimization of two multidimensional PESs, including a differentiable model PES of a DNA chain with D = 50 adenine-thymine base pairs, and a discrete non-differentiable potential energy surface, V(p) = mod(N,p), that resolves the prime factors of an integer N, with p in the space of prime numbers {2, 3,..., pmax} folded as a d-dimensional 21 × 22 × ··· × 2d tensor. We find that IPA resolves multiple degenerate global minima even when separated by large energy barriers in the highly rugged landscape of the potentials. Therefore, IPA should be of great interest for a wide range of other optimization problems ubiquitous in molecular and electronic structure calculations.

Let $$\mathcal {P}_r$$ denote an almost-prime with at most r prime factors, counted according to multiplicity. In this paper, we establish a theorem of Bombieri–Vinogradov type for the Piatetski–Shapiro primes $$p=[n^{1/\gamma }]$$ with $$\frac{85}{86}

In Sarkozy (2001) the third author of this paper presented two conjectures on the additive decomposability of the sequence of ”smooth” (or ”friable”) numbers. Elsholtz and Harper (2015) proved (by using sieve methods) the second (less demanding) conjecture. The goal of this paper is to extend and sharpen their result in three directions by using a different approach (based on the theory of S -unit equations).

Let $${\mathfrak {B}}(x)$$ be the number of composite positive integers up to x whose sum of distinct prime factors is a prime number. Luca and Moodley proved that there exist two positive constants $$a_1$$ and $$a_2$$ such that $$\begin{aligned} a_1x/\log ^3x\le {\mathfrak {B}}(x)\le a_2x/\log x. \end{aligned}$$ Assuming a uniform version of the Bateman–Horn conjecture, they gave a conditional proof of a lower bound of the same order of magnitude as the upper bound. In this paper, we offer an unconditional proof of the this result, i.e., $$\begin{aligned} {\mathfrak {B}}(x)\asymp \frac{x}{\log x}. \end{aligned}$$

An upper quasi-density on $\bf H$ (the integers or the non-negative integers) is a real-valued subadditive function $\mu^\ast$ defined on the whole power set of $\mathbf H$ such that $\mu^\ast(X) \le \mu^\ast({\bf H}) = 1$ and $\mu^\ast(k \cdot X + h) = \frac{1}{k}\, \mu^\ast(X)$ for all $X \subseteq \bf H$, $k \in {\bf N}^+$, and $h \in \bf N$, where $k \cdot X := \{kx: x \in X\}$; and an upper density on $\bf H$ is an upper quasi-density on $\bf H$ that is non-decreasing with respect to inclusion. We say that a set $X \subseteq \bf H$ is small if $\mu^\ast(X) = 0$ for every upper quasi-density $\mu^\ast$ on $\bf H$. Main examples of upper densities are given by the upper analytic, upper Banach, upper Buck, and upper P\'olya densities, along with the uncountable family of upper $\alpha$-densities, where $\alpha$ is a real parameter $\ge -1$ (most notably, $\alpha = -1$ corresponds to the upper logarithmic density, and $\alpha = 0$ to the upper asymptotic density). It turns out that a subset of $\bf H$ is small if and only if it belongs to the zero set of the upper Buck density on $\bf Z$. This allows us to show that many interesting sets are small, including the integers with less than a fixed number of prime factors, counted with multiplicity; the numbers represented by a binary quadratic form with integer coefficients whose discriminant is not a perfect square; and the image of $\bf Z$ through a non-linear integral polynomial in one variable., Comment: 15 pp, no figures. The paper is a sequel of arXiv:1506.04664. Fixed minor details. To appear in The Ramanujan Journal

Let $$\mathcal {P}_r$$ denote an almost-prime with at most r prime factors, counted according to multiplicity. In this paper, we generalize the result of Vaughan (Bull Lond Math Soc 17(1):17–20, 1985) for ternary ‘admissible exponent’. Moreover, we use the refined ‘admissible exponent’ to prove that, for $$3\leqslant k\leqslant 14$$ and for every sufficiently large even integer n, the following equation $$\begin{aligned} n=x^2+p_1^2+p_2^3+p_3^3+p_4^3+p_5^k \end{aligned}$$ is solvable with x being an almost-prime $$\mathcal {P}_{r(k)}$$ and the other variables primes, where r(k) is defined in Theorem 1.1. This result constitutes a deepening of previous results.

We examine oscillations in a number of sums of arithmetic functions involving [Formula: see text], the total number of prime factors of [Formula: see text], and [Formula: see text], the number of distinct prime factors of [Formula: see text]. In particular, we examine oscillations in [Formula: see text] and in [Formula: see text] for [Formula: see text], and in [Formula: see text]. We show for example that each of the inequalities [Formula: see text], [Formula: see text], [Formula: see text], and [Formula: see text] is true infinitely often, disproving some hypotheses of Sun.

Erdős proved that F ( A ) : = ∑ a ∈ A 1 a log ⁡ a converges for any primitive set of integers A and later conjectured this sum is maximized when A is the set of primes. Banks and Martin further conjectured that F ( P 1 ) > ⋯ > F ( P k ) > F ( P k + 1 ) > ⋯ , where P j is the set of integers with j prime factors counting multiplicity, though this was recently disproven by Lichtman. We consider the corresponding problems over the function field F q [ x ] , investigating the sum F ( A ) : = ∑ f ∈ A 1 deg f ⋅ q deg f . We establish a uniform bound for F ( A ) over all primitive sets of polynomials A ⊂ F q [ x ] and conjecture that it is maximized by the set of monic irreducible polynomials. We find that the analogue of the Banks-Martin conjecture is false for q = 2 , 3, and 4, but we find computational evidence that it holds for q > 4 .

In 1976, Mahler posed the question about the existence of a transcendental function f ∈ Z { z } with bounded coefficients and such that f ( Q ‾ ∩ B ( 0 , 1 ) ) ⊆ Q ‾ . In this paper, we prove, in particular, the existence of such a function but with the weaker requirement that the coefficients have only 2 and 3 as prime factors. More generally, we shall prove that any subset of Q ‾ ∩ B ( 0 , 1 ) , which is closed under complex conjugation and which contains the element 0, is the exceptional set of uncountably many transcendental functions in Z { z } with coefficients having only 2 and 3 as prime factors.

Generalizing the concept of a perfect number is a Zumkeller or integer perfect number that was introduced by Zumkeller in 2003. The positive integer $n$ is a Zumkeller number if its divisors can be partitioned into two sets with the same sum, which will be $\sigma(n)/2$. Generalizing even further, we call $n$ a $k$-layered number if its divisors can be partitioned into $k$ sets with equal sum. In this paper, we completely characterize Zumkeller numbers with two distinct prime factors and give some bounds for prime factorization in case of Zumkeller numbers with more than two distinct prime factors. We also characterize $k$-layered numbers with two distinct prime factors and even $k$-layered numbers with more than two distinct odd prime factors. Some other results concerning these numbers and their relationship with practical numbers and Harmonic mean numbers are also discussed., Comment: 14 pages, accepted version, to appear in the Journal of Number Theory

Let A be the direct product of a cyclic group of order $$2^u$$ with $$u\ge 1$$ and a cyclic group of order $$2^v$$ with $$u\ge v\ge 0$$ . There are some 2-adic properties of the number $$h(A,A_n)$$ of homomorphisms from A to the alternating group $$A_n$$ on n-letters, which are similar to those of the number of homomorphisms from A to the symmetric group on n-letters. The exponent of 2 in the decomposition of $$h(A,A_n)$$ into prime factors is denoted by $${\mathrm {ord}}_2(h(A,A_n))$$ . Let [x] denote the largest integer not exceeding a real number x. For any nonnegative integer n, the lower bound of $${\mathrm {ord}}_2(h(A,A_n))$$ is $$\sum _{j=1}^u[n/2^j]+[n/2^{u+2}]-[n/2^{u+3}]-1$$ if $$u=v\ge 1$$ , and is $$\sum _{j=1}^u[n/2^j]-(u-v)[n/2^{u+1}]-1$$ otherwise. For any positive odd integer y, $${\mathrm {ord}}_2(h(A,A_{2^{u+1}y}))$$ and $${\mathrm {ord}}_2(h(A,A_{2^{u+1}y+1}))$$ are described by certain 2-adic integers if either $$u\ge v+2\ge 3$$ or $$u\ge 1$$ and $$v=0$$ . The values $$\{h(A,A_n)\}_{n=0}^\infty $$ are explained by certain 2-adic analytic functions unless $$u=v+1\ge 2$$ . The results are obtained by using the generating function $$\sum _{n=0}^\infty h(A,A_n)X^n/n!$$ .

In this paper we study smooth orientation-preserving free actions of the cyclic group $\mathbb Z/m$ on a class of $(n-1)$-connected $2n$-manifolds, $\sharp g (S^n \times S^n)\sharp \Sigma$, where $\Sigma$ is a homotopy $2n$-sphere. When $n=2$ we obtain a classification up to topological conjugation. When $n=3$ we obtain a classification up to smooth conjugation. When $n \ge 4$ we obtain a classification up to smooth conjugation when the prime factors of $m$ are larger than a constant $C(n)$., Comment: 18 pages

In this paper, for a positive integer n ≥ 1, we look at the size and prime factors of the iterates of the Ramanujan τ function applied to n.

In this manuscript we discuss the notion of (statistical) independence embedded in its historical context. We focus in particular on its appearance and role in number theory, concomitantly exploring the intimate connection of independence and the famous Gaussian law of errors. As we shall see, this at times requires us to go adrift from the celebrated Kolmogorov axioms, which give the appearance of being ultimate ever since they have been introduced in the 1930s. While these insights are known to many a mathematician, we feel it is time for both a reminder and renewed awareness. Among other things, we present the independence of the coefficients in a binary expansion together with a central limit theorem for the sum-of-digits function as well as the independence of divisibility by primes and the resulting, famous central limit theorem of Paul Erdős and Mark Kac on the number of different prime factors of a number $$n\in{\mathbb{N}}$$ n ∈ N . We shall also present some of the (modern) developments in the framework of lacunary series that have its origin in a work of Raphaël Salem and Antoni Zygmund.

Modern beam shaping techniques have enabled the generation of optical fields displaying a wealth of structural features, which include three-dimensional topologies such as Möbius, ribbon strips and knots. However, unlike simpler types of structured light, the topological properties of these optical fields have hitherto remained more of a fundamental curiosity as opposed to a feature that can be applied in modern technologies. Due to their robustness against external perturbations, topological invariants in physical systems are increasingly being considered as a means to encode information. Hence, structured light with topological properties could potentially be used for such purposes. Here, we introduce the experimental realization of structures known as framed knots within optical polarization fields. We further develop a protocol in which the topological properties of framed knots are used in conjunction with prime factorization to encode information., Beam shaping methods can generate optical fields with nontrivial topologies, which are invariant against perturbations and thus interesting for information encoding. Here, the authors introduce the realization of framed optical knots to encode programs with the conjoined use of prime factorization.

Let $X_{n}$ denote the unitary Cayley graph of $\mathbb{Z}/n\mathbb{Z}$. We continue the study of cases in which the inequality $\gamma_t(X_n) \le g(n)$ is strict, where $\gamma_t$ denotes the total domination number, and $g$ is the arithmetic function known as Jacobsthal's function. The best that is currently known in this direction is a construction of Burcroff which gives a family of $n$ with arbitrarily many prime factors that satisfy $\gamma_t(X_n) \le g(n)-2$. We present a new interpretation of the problem which allows us to use recent results on the computation of Jacobsthal's function to construct $n$ with arbitrarily many prime factors that satisfy $\gamma_t(X_n) \le g(n)-16$. We also present new lower bounds on the domination numbers of direct products of complete graphs, which in turn allow us to derive new asymptotic lower bounds on $\gamma(X_n)$, where $\gamma$ denotes the domination number. Finally, resolving a question of Defant and Iyer, we completely classify all graphs $G = \prod_{i=1}^t K_{n_i}$ satisfying $\gamma(G) = t+2$., Comment: 15 pages

There have been several efforts to apply quantum SAT solving methods to factor large integers. While these methods may provide insight into quantum SAT solving, to date they have not led to a convincing path to integer factorization that is competitive with the best known classical method, the Number Field Sieve. Many of the techniques tried involved directly encoding multiplication to SAT or an equivalent NP-hard problem and looking for satisfying assignments of the variables representing the prime factors. The main challenge in these cases is that, to compete with the Number Field Sieve, the quantum SAT solver would need to be superpolynomially faster than classical SAT solvers. In this paper the use of SAT solvers is restricted to a smaller task related to factoring: finding smooth numbers, which is an essential step of the Number Field Sieve. We present a SAT circuit that can be given to quantum SAT solvers such as annealers in order to perform this step of factoring. If quantum SAT solvers achieve any asymptotic speedup over classical brute-force search for smooth numbers, then our factoring algorithm is faster than the classical NFS.

Some new results concerning the equation $\sigma(N)=aM, \sigma(M)=bN$ are proved. As a corollary, there are only finitely many odd superperfect numbers with a fixed number of distinct prime factors., Comment: 14 pages, the author's final version, with the link to Western Number Theory Problems updated

Let $\mathcal{C}$ be a fusion category over an algebraically closed field $\mathbb{k}$ of arbitrary characteristic. Two numerical invariants of $\mathcal{C}$ , that is, the Casimir number and the determinant of $\mathcal{C}$ are considered in this paper. These two numbers are both positive integers and admit the property that the Grothendieck algebra $(\mathcal{C})\otimes_{\mathbb{Z}}K$ over any field K is semisimple if and only if any of these numbers is not zero in K. This shows that these two numbers have the same prime factors. If moreover $\mathcal{C}$ is pivotal, it gives a numerical criterion that $\mathcal{C}$ is nondegenerate if and only if any of these numbers is not zero in $\mathbb{k}$ . For the case that $\mathcal{C}$ is a spherical fusion category over the field $\mathbb{C}$ of complex numbers, these two numbers and the Frobenius–Schur exponent of $\mathcal{C}$ share the same prime factors. This may be thought of as another version of the Cauchy theorem for spherical fusion categories.

In this text we show that one can generalize results showing that $$\mathrm {CH}^2(X)$$ , for various Severi–Brauer varieties X, is sometimes torsion free. In particular we show that for any pair of odd integers (n, m), with m dividing n and sharing the same prime factors, one can find a central simple k-algebra A of index n and exponent m that moreover has $$\mathrm {CH}^2(X)$$ torsion free for $$X=\mathrm {SB}(A)$$ . One can even take $$k={\mathbb {Q}}$$ in this construction.

In order to study integers with few prime factors, the average of $\unicode[STIX]{x1D6EC}_{k}=\unicode[STIX]{x1D707}\ast \log ^{k}$ has been a central object of research. One of the more important cases, $k=2$ , was considered by Selberg [‘An elementary proof of the prime-number theorem’, Ann. of Math. (2)50 (1949), 305–313]. For $k\geq 2$ , it was studied by Bombieri [‘The asymptotic sieve’, Rend. Accad. Naz. XL (5)1(2) (1975/76), 243–269; (1977)] and later by Friedlander and Iwaniec [‘On Bombieri’s asymptotic sieve’, Ann. Sc. Norm. Super. Pisa Cl. Sci. (4)5(4) (1978), 719–756], as an application of the asymptotic sieve. Let $\unicode[STIX]{x1D6EC}_{j,k}:=\unicode[STIX]{x1D707}_{j}\ast \log ^{k}$ , where $\unicode[STIX]{x1D707}_{j}$ denotes the Liouville function for $(j+1)$ -free integers, and $0$ otherwise. In this paper we evaluate the average value of $\unicode[STIX]{x1D6EC}_{j,k}$ in a residue class $n\equiv a\text{ mod }q$ , $(a,q)=1$ , uniformly on $q$ . When $j\geq 2$ , we find that the average value in a residue class differs by a constant factor from the expected value. Moreover, an explicit formula of Weil type for $\unicode[STIX]{x1D6EC}_{k}(n)$ involving the zeros of the Riemann zeta function is derived for an arbitrary compactly supported ${\mathcal{C}}^{2}$ function.

We consider the isomorphism problem for groups specified by their multiplication tables. Until recently, the best published bound for the worst-case was achieved by the n^(log_p n + O(1)) generator-enumeration algorithm. In previous work with Fabian Wagner, we showed an n^((1 / 2) log_p n + O(log n / log log n)) time algorithm for testing isomorphism of p-groups by building graphs with degree bounded by p + O(1) that represent composition series for the groups and applying Luks' algorithm for testing isomorphism of bounded degree graphs. In this work, we extend this improvement to the more general class of solvable groups to obtain an n^((1 / 2) log_p n + O(log n / log log n)) time algorithm. In the case of solvable groups, the composition factors can be large which prevents previous methods from outperforming the generator-enumeration algorithm. Using Hall's theory of Sylow bases, we define a new object that generalizes the notion of a composition series with small factors but exists even when the composition factors are large. By constructing graphs that represent these objects and running Luks' algorithm, we obtain our algorithm for solvable-group isomorphism. We also extend our algorithm to compute canonical forms of solvable groups while retaining the same complexity., Comment: 22 pages. This is an updated and improved version of the results for solvable groups in arXiv:1205.0642

For each integer m ≥ 2 , every Boolean function f can be expressed as a unique multilinear polynomial modulo m, and the degree of this multilinear polynomial is called its modulo m degree. In this paper we investigate the modulo degree complexity of total Boolean functions initiated by Parikshit Gopalan et al. [9] , in which they asked the following question: whether the degree complexity of a Boolean function is polynomially related with its modulo m degree. For m be a power of primes, it is already known that the module m degree can be arbitrarily smaller compare to the degree complexity (see Section 2 for details). When m has at least two distinct prime factors, the question remains open. Towards this question, our results include: (1) we obtain some nontrivial equivalent forms of this question; (2) we affirm this question for some special classes of functions; (3) we prove a no-go theorem, explaining why this problem is difficult to attack from the computational complexity point of view; (4) we show a super-linear separation between the degree complexity and the modulo m degree.

We obtain a lower bound on the largest prime factor of the denominator of rational numbers in the Cantor set. This gives a stronger version of a recent result of Schleischitz [‘On intrinsic and extrinsic rational approximation to Cantor sets’, Ergodic Theory Dyn. Syst. to appear] obtained via a different argument.

An arithmetical structure on the complete graph $K_n$ with $n$ vertices is given by a collection of $n$ positive integers with no common factor each of which divides their sum. We show that, for all positive integers $c$ less than a certain bound depending on $n$, there is an arithmetical structure on $K_n$ with largest value $c$. We also show that, if each prime factor of $c$ is greater than $(n+1)^2/4$, there is no arithmetical structure on $K_n$ with largest value $c$. We apply these results to study which prime numbers can occur as the largest value of an arithmetical structure on $K_n$., Comment: 10 pages; v2: minor corrections

In this paper, it is proved that the finite group G is solvable if cod $$(\chi ) \le p_{\chi }\cdot \chi (1)$$ for any nonlinear irreducible character $$\chi $$ of G, where $$p_{\chi }$$ is the largest prime divisor of $$|G:\mathrm{ker} \chi |$$ .

One problem that arises in computation involving large numbers is precision. In certain situations, the result might be represented by the standard data type, but arithmetic precision might be compromised when dealing with large numbers in the course to the result. Binomial coefficients are an example that suffer from this torment. In the present paper, we review numerical methods to compute the binomial coefficients: Pascal’s recursive method; prime factorization to cancel out terms; gamma function approximation; and a simplified iterative method that avoids loss in precision. Acknowledging that the binomial coefficients might be obtained by a successive convolution of a simple discrete rectangular function, we propose a different approach based on the discrete Fourier transform and another based on its fast implementation. We analyze and compare performance and precision of all of them. The proposed methods overcome the previous ones when computing all coefficients for a given level n, attaining better precision for large values of n.

We prove that for the Steinhaus Random Variable [Formula: see text], [Formula: see text] where [Formula: see text] and [Formula: see text] denotes the number of prime factors of [Formula: see text].

Let λ2 ∈ ℕ, and in dimensions d ≥ 5, let Aλf(x) denote the average of f: ℤd → ℝ over the lattice points on the sphere of radius λ centered at x. We prove lp improving properties of Aλ: $$\begin{array}{*{20}{c}} {{{\left\| {{A_\lambda }} \right\|}_{{\ell ^{p \to }}{\ell ^{p'}}}} \leqslant {C_{d,p,\omega ({\lambda ^2})}}{\lambda ^{(1 - \tfrac{2}{p})}},}&{\frac{{d - 1}}{{d + 1}} < p \leqslant \frac{d}{{d - 2}}} \end{array}.$$ It holds in dimension d = 4 for odd λ2. The dependence is in terms of ω(λ2), the number of distinct prime factors of λ2. These inequalities are discrete versions of a classical inequality of Littman and Strichartz on the Lp improving property of spherical averages on ℝd. In particular they are scale free, in a natural sense. The proof uses the decomposition of the corresponding multiplier whose properties were established by Magyar–Stein–Wainger, and Magyar. We then use a proof strategy of Bourgain, which dominates each part of the decomposition by an endpoint estimate.

We determine, up to multiplicative constants, the number of integers $n\leq x$ that have a divisor in $(y,2y]$ and no prime factor $\leq w$ . Our estimate is uniform in $x,y,w$ . We apply this to determine the order of the number of distinct integers in the $N\times N$ multiplication table, which are free of prime factors $\leq w$ , and the number of distinct fractions of the form $(a_{1}a_{2})/(b_{1}b_{2})$ with $1\leq a_{1}\leq b_{1}\leq N$ and $1\leq a_{2}\leq b_{2}\leq N$ .

Denote by P the set of all primes and by P + ( n ) the largest prime factor of integer n ⩾ 1 with the convention P + ( 1 ) = 1 . For each η > 1 , let c = c ( η ) > 1 be some constant depending on η and P a , c , η : = { p ∈ P : p = P + ( q − a ) for some prime q with p η q ⩽ c ( η ) p η } . In this paper, under the Elliott-Halberstam conjecture we prove, for y → ∞ , π a , c , η ( x ) : = | ( 1 , x ] ∩ P a , c , η | ∼ π ( x ) or π a , c , η ( x ) ≫ a , η π ( x ) according to values of η. These are complement for some results of Banks-Shparlinski [1] , of Wu [12] and of Chen-Wu [2] .

International audience; We establish new Bombieri-Vinogradov type estimates for a wide class of multiplicative arithmetic functions and derive several applications, including: a new proof of a recent estimate by Drappeau and Topacogullari for arithmetical correlations; a theorem of Erdős-Wintner type with support equal to the level set of an additive function at shifted argument; and a law of iterated logarithm for the distribution of prime factors of integers weighted by τ (n − 1) where τ denotes the divisor function.

We revisit the problem of integer factorization with number-theoretic oracles, including a well-known problem: can we factor an integer $N$ unconditionally, in deterministic polynomial time, given the value of the Euler totient $ϕ(N)$? We show that this can be done, under certain size conditions on the prime factors of N. The key technique is lattice basis reduction using the LLL algorithm. Among our results, we show for example that if $N$ is a squarefree integer with a prime factor $p > √ N$ , then we can recover p in deterministic polynomial time given $ϕ(N)$. We also shed some light on the analogous problems for Carmichael's function, and the order oracle that is used in Shor's quantum factoring algorithm.

The public parameters of the RSA cryptosystem are represented by the pair of integers N and e . In this work, first we show that if e satisfies the Diophantine equation of the form e x 2 − ϕ ( N ) y 2 = z for appropriate values of x , y and z under certain specified conditions, then one is able to factor N . That is, the unknown y x can be found amongst the convergents of e N via continued fractions algorithm. Consequently, Coppersmith’s theorem is applied to solve for prime factors p and q in polynomial time. We also report a second weakness that enabled us to factor k instances of RSA moduli simultaneously from the given ( N i , e i ) for i = 1 , 2 , ⋯ , k and a fixed x that fulfills the Diophantine equation e i x 2 − y i 2 ϕ ( N i ) = z i . This weakness was identified by solving the simultaneous Diophantine approximations using the lattice basis reduction technique. We note that this work extends the bound of insecure RSA decryption exponents.

Given a function field $K$ and $\phi \in K[x]$, we study two finiteness questions related to iteration of $\phi$: whether all but finitely many terms of an orbit of $\phi$ must possess a primitive prime divisor, and whether the Galois groups of iterates of $\phi$ must have finite index in their natural overgroup $\text{Aut}(T_d)$, where $T_d$ is the infinite tree of iterated preimages of $0$ under $\phi$. We focus particularly on the case where $K$ has characteristic $p$, where far less is known. We resolve the first question in the affirmative under relatively weak hypotheses; interestingly, the main step in our proof is to rule out "Riccati differential equations" in backwards orbits. We then apply our result on primitive prime divisors and adapt a method of Looper to produce a family of polynomials for which the second question has an affirmative answer; these are the first non-isotrivial examples of such polynomials. We also prove that almost all quadratic polynomials over $\mathbb{Q}(t)$ have iterates whose Galois group is all of $\text{Aut}(T_d)$.

Numerical experiments suggest that there are more prime factors in certain arithmetic progressions than others. Greg Martin conjectured that the function $\sum _{n\leq x, n\equiv 1 \bmod 4} \omega (n)-\sum _{n\leq x, n\equiv 3 \bmod 4} \omega (n)$ will attain a constant sign as $x\rightarrow \infty $, where $\omega (n)$ is the number of distinct prime factors of $n$. In this paper, we prove explicit formulas for both $\sum _{n\leq x}\chi (n)\Omega (n)$ and $\sum _{n\leq x}\chi (n)\omega (n)$ under some reasonable assumptions, where $\chi (n)$ is a Dirichlet character and $\Omega (n)$ is the number of prime factors of $n$ counted with multiplicity. Our results give strong evidence for Martin’s conjecture.

In this paper, we will use Maynard's method [5] to prove that for any positive integer m, there exists infinitely many integers n with at most two prime factors that can be written in the form p + 2 l in at least m + 1 different ways.

There have been several works for studying the security of CRT-RSA with small CRT exponents d p and d q by using lattice-based Coppersmith's method. Thus far, two attack scenarios have been mainly studied: (1) d q is small with unbalanced prime factors p ≪ q . (2) Both d p and d q are small for balanced p ≈ q . The best attacks for the both scenarios were proposed by Takayasu-Lu-Peng (Eurocrypt'17, Journal of Cryptology'19) and the attack conditions are much better than the other known attacks. Although the attacks have been very useful for studying the security of CRT-RSA, the structures of their proposed lattices are not well understood. In this paper, to further study the security of CRT-RSA, we first define a generalized attack scenario to unify the previous ones. Specifically, all p , q , d p , and d q can be of arbitrary sizes. Furthermore, we propose improved attacks in this paper when d p and/or p is sufficiently small. Technically, we construct a lattice whose basis vectors are chosen flexibly depending on the sizes of p , q , d p , and d q . Since the attack scenarios (1) and (2) are simpler than our general scenario, the previous Takayasu-Lu-Peng's lattices are simple special cases of ours. We are able to achieve the flexible lattice constructions by exploiting implicit but essential structures of Takayasu-Lu-Peng's lattices. We check the validity of our proposed attacks by computer experiments. We believe that the deeper understanding of the lattice structures will be useful for studying the security of CRT-RSA even in other scenarios.

Recently, Gerhard J. Woeginger [1] gave a survey on the interesting history of results on equiangular n-vertex polygons with edge lengths in arithmetic progression. Such a polygon exists if, and only if, n has at least two distinct prime factors.

In an earlier paper we considered the distribution of integers $n$ for which Euler’s totient function at $n$ has all small prime factors. Here we obtain an improvement that is likely to be best possible.

Given a positive integer n let ω (n) denote the number of distinct prime factors of n, and let a be fixed positive integer. Extending work of Kubilius, we develop a bivariate probabilistic model to study the joint distribution of the deterministic vectors (ω(n), ω(n + a)), with n ≤ x as x → ∞, where n and n + a belong to a subset of ℕ with suitable properties. We thus establish a quantitative version of a bivariate analogue of the Erdős–Kac theorem on proper subsets of ℕ.We give three applications of this result. First, if y = x0(1) is not too small then we prove (in a quantitative way) that the y-truncated Möbius function μy has small binary autocorrelations. This gives a new proof of a result due to Daboussi and Sarkőzy. Second, if μ(n; u) :=e(uω(n)), where u ∈ ℝ then we show that μ(.; u) also has small binary autocorrelations whenever u = o(1) and $u\sqrt {\mathop {\log }\nolimits_2 x} \to \infty$, as x → ∞. These can be viewed as partial results in the direction of a conjecture of Chowla on binary correlations of the Möbius function.Our final application is related to a problem of Erdős and Mirsky on the number of consecutive integers less than x with the same number of divisors. If $y = x^{{1 \over \beta }}$, where β = β(x) satisfies certain mild growth conditions, we prove a lower bound for the number of consecutive integers n ≤ x that have the same number of y-smooth divisors. Our bound matches the order of magnitude of the one conjectured for the original Erdős-Mirsky problem.

Bang (1886), Zsigmondy (1892) and Birkhoff and Vandiver (1904) initiated the study of the largest prime divisors of sequences of the form a n − b n , denoted P ( a n − b n ) , by essentially proving that for integers a > b > 0 , P ( a n − b n ) ≥ n + 1 for every n > 2 . Since then, the problem of finding bounds on the largest prime factor of Lehmer sequences, Lucas sequences or special cases thereof has been studied by many, most notably by Schinzel (1962), and Stewart (1975, 2013). In 2002, Murty and Wong proved, conditionally upon the abc conjecture, that P ( a n − b n ) ≫ n 2 − ϵ for any ϵ > 0 . In this article, we improve this result for the specific case where b = 1 . Specifically, we obtain a more precise result, and one that is dependent on a condition we believe to be weaker than the abc conjecture. Our result actually concerns the largest prime factor of the nth cyclotomic polynomial evaluated at a fixed integer a, P ( Φ n ( a ) ) , as we let n grow. We additionally prove some results related to the prime factorization of Φ n ( a ) . We also present a connection to Wieferich primes, as well as show that the finiteness of a particular subset of Wieferich primes is a sufficient condition for the infinitude of non-Wieferich primes. Finally, we use the technique used in the proof of the aforementioned results to show an improvement on average of estimates due to Erdős for certain sums.

International audience; Investigating a question of Alladi, we describe the local distribution of small prime factors of integers, with emphasis on the transition phase occurring for certain values of the parameters.

We obtain uniform estimates for $N_k(x,y)$, the number of positive integers $n$ up to $x$ for which $\omega_y(n)=k$, where $\omega_y(n)$ is the number of distinct prime factors of $n$ which are $0$ by the Buchstab-de Bruijn method. We also utilize a certain recent result of Tenenbaum to complete our asymptotic analysis., Comment: 33 pages