Search

Let ω ( n ) denote the number of distinct prime factors of n and let τ k ( n ) denote the k-fold divisor function. Adapting a method of Granville and Soundararajan, we evaluate the centralized moments of ω ( n ) , weighted by τ k ( n ) , and deduce a weighted version of the Erdős-Kac Theorem.

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.

We study the normal number of prime factors of a f ( p ) + a g ( p ) with p prime and f , g distinct Hecke eigenforms of weight two. Assuming a quasi-generalized Riemann hypothesis, we show that the normal order is log log p . We also obtain an estimate for the number of primes p for which a f ( p ) + a g ( p ) = 0 .

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.

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.

Algorithms for interpolating a polynomial f from its evaluation points whose running time depends on the sparsity to f the polynomial when it is represented as a linear combination of t Chebyshev Polynomials of the First Kind with non-zero scalar coefficients are given by Lakshman and Saunders (1995), Kaltofen and Lee (2003) and Arnold and Kaltofen (2015). The term degrees are computed from values of Chebyshev Polynomials of those degrees. We give an algorithm that computes those degrees in the manner of the Pohlig and Hellman algorithm (1978) for computing discrete logarithms modulo a prime number p when the factorization of p - 1(or p + 1) has small prime factors, that is, when p - 1(or p + 1) is smooth. Our algorithm can determine the Chebyshev degrees modulo such primes in bit complexity log(p)(O(1)) times the squareroot of the largest prime factor of p - 1( or p + 1). (C) 2020 Elsevier Ltd. All rights reserved. National Science FoundationNational Science Foundation (NSF) [CCF-1421128, CCF-1708884] Supported by National Science Foundation CCF-1421128 and CCF-1708884.

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).

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 this paper, we prove a generalization of a conjecture of Erdos, about the chromatic number of certain Kneser-type hypergraphs. For integers n , k , r , s with n ≥ r k and 2 ≤ s ≤ r , the r-uniform general Kneser hypergraph KG s r ( n , k ) , has all k-subsets of { 1 , … , n } as the vertex set and all multi-sets { A 1 , … , A r } of k-subsets with s-wise empty intersections as the edge set. The case r = s = 2 , was considered by Kneser [7] in 1955, where he conjectured that its chromatic number is n − 2 ( k − 1 ) . This was finally proved by Lovasz [9] in 1978. The case r > 2 and s = 2 , was considered by Erdos in 1973, and he conjectured that its chromatic number is ⌈ n − r ( k − 1 ) r − 1 ⌉ . This conjecture was proved by Alon, Frankl and Lovasz [2] in 1986. The case where s > 2 , was considered by Sarkaria [11] in 1990, where he claimed to prove a lower bound for its chromatic number which generalized all previous results. Unfortunately, an error was found by Lange and Ziegler [14] in 2006 in the induction method of Sarkaria on the number of prime factors of r, and Sarkaria's proof only worked when s is less than the smallest prime factor of r or s = 2 . Finally in 2019, Aslam, Chen, Coldren, Frick and Setiabrata [3] were able to extend this by using methods different from Sarkaria to the case when r = 2 α 0 p 1 α 1 … p t α t and 2 ≤ s ≤ 2 α 0 ( p 1 − 1 ) α 1 … ( p t − 1 ) α t . In this paper, by applying the Z p -Tucker lemma of Ziegler [13] and Meunier [10] , we finally prove the general Erdos conjecture and prove the claimed result of Sarkaria for any 2 ≤ s ≤ r . We also provide another proof of a special case of this result, using methods similar to those of Alon, Frankl, and Lovasz [2] and compute the connectivity of certain simplicial complexes that might be of interest in their own right.

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 $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

Let ω ( n ) denote the number of distinct prime factors of the positive integer n. In 1917, Hardy and Ramanujan showed that for all real numbers x ≥ 2 and all positive integers k, ∑ n ≤ x ω ( n ) = k 1 ≤ C x log ⁡ x ( log ⁡ log ⁡ x + D ) k − 1 ( k − 1 ) ! , where C and D are absolute constants. We derive an analogous result when the summand 1 is replaced by f ( n ) , for many nonnegative multiplicative functions f. Summing on k recovers a frequently-used mean-value theorem of Hall and Tenenbaum. We use the same idea to establish a variant of a theorem of Shirokov, concerning multiplicative functions that are o ( 1 ) on average at the primes.

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.

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] .

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.

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.

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.

We extend results about asymmetric colorings of finite Cartesian products of graphs to strong and direct products of graphs and digraphs. On the way we shorten proofs for the existence of prime factorizations of finite digraphs and characterize the structure of the automorphism groups of strong and direct products. The paper ends with results on asymmetric colorings of Cartesian products of finite and infinite digraphs.

We settle a conjecture of Cerone and Dragomir on the concavity of the reciprocal of the Riemann zeta function on ( 1 , ∞ ) . It is further shown in general that reciprocals of a family of zeta functions arising from semigroups of integers are also concave on ( 1 , ∞ ) , thereby giving a positive answer to a question posed by Cerone and Dragomir on the existence of such zeta functions. As a consequence of our approach, weighted type Mertens sums over semigroups of integers are seen to be biased in favor of square-free integers with an odd number of prime factors. To strengthen the already known log-convexity property of Dirichlet series with positive coefficients, the geometric convexity of a large class of zeta functions is obtained and this in turn leads to generalizations of certain inequalities on the values of these functions due to Alzer, Cerone and Dragomir.

We construct several new families of non-congruent numbers with arbitrarily many prime factors congruent to 3 modulo 8. Our results generalize the work of Reinholz, Spearman and Yang [14] . Our methods are based on Monsky's formula on the 2-Selmer rank of the congruent elliptic curve and the recent results by Tian, Yuan and Zhang on the congruent number problem.

Integer division and perfect powers play a central role in numerous mathematical results, especially in number theory. Classical examples involve perfect squares like in Pythagora's theorem, or higher perfect powers as the conjectures of Fermat (solved in 1994 by A. Wiles [Wiles, A.J., Modular elliptic curves and Fermat's Last Theorem, Annals of Mathematics, 141 (1995), 443–551.]) or Catalan (solved in 2002 by P. Mihailescu [Mihailescu, P., Primary cyclotomic units and a proof of Catalan's conjecture, J. Reine Angew. Math., 572 (2004), 167–195.]). The purpose of this paper is two-fold. First, we present some new integer sequences a ( n ) , counting the positive integers smaller than n, having a maximal prime factor. We introduce an arithmetic function counting the number of perfect powers i j obtained for 1 ≤ i , j ≤ n . Along with some properties of this function, we present the sequence A303748, which was recently added to the Online Encyclopedia of Integer Sequences (OEIS) [The On-Line Encyclopedia of Integer Sequences, http://oeis.org , OEIS Foundation Inc. 2011.]. Finally, we discuss some other novel integer sequences.

In this paper we give a complete classification of strongly square-free reflective Z -lattices of signature ( 5 , 1 ) . This is done by reducing the classification of Lorentzian lattices to those of positive-definite lattices. The classification of totally-reflective genera breaks up into two parts. The first part consists of classifying the square free, totally-reflective, primitive genera by calculating strong bounds on the prime factors of the determinant of positive-definite quadratic forms (lattices) with this property. We achieve these bounds by combining the Minkowski–Siegel mass formula with the combinatorial classification of reflective lattices accomplished by Scharlau & Blaschke. In a second part, we use a lattice transformation that goes back to Watson, to generate all totally-reflective, primitive genera when starting from the square free case.

We find a complete criterion for a Kummer extension K over the rational function field k = F q ( T ) of degree l to have indivisibility of its divisor class number h K by l, where F q is the finite field of order q and l is a prime divisor of q − 1 . More importantly, when h K is not divisible by l, we have h K ≡ 1 ( mod l ) . In fact, the indivisibility of h K by l depends on the number of finite primes ramified in K / k and whether or not the infinite prime of k is unramified in K. Using this criterion, we explicitly construct an infinite family of the maximal real cyclotomic function fields whose divisor class numbers are divisible by l.

For positive integers k and n with k ⩽ n − 1 , let P n , k ( x ) denote the polynomial ∑ j = 0 k ( n j ) x j , where ( n j ) = n ! j ! ( n − j ) ! . In 2011, Khanduja, Khassa and Laishram proved the irreducibility of P n , k ( x ) over the field Q of rational numbers for those n , k for which 2 ≤ 2 k ≤ n ( k + 1 ) 3 . In this paper, we extend the above result and prove that if 2 ≤ 2 k ≤ n ( k + 1 ) e + 1 for some positive integer e and the smallest prime factor of k is greater than e, then there exists an explicitly constructible constant C e depending only on e such that the polynomial P n , k ( x ) is irreducible over Q for k ≥ C e .

The unitary Cayley graph of $\mathbb{Z} /n \mathbb{Z}$, denoted $X_{\mathbb{Z} / n \mathbb{Z}}$, has vertices $0,1, \dots, n-1$ with $x$ adjacent to $y$ if $x-y$ is relatively prime to $n$. We present results on the tightness of the known inequality $\gamma(X_{\mathbb{Z} / n \mathbb{Z}})\leq \gamma_t(X_{\mathbb{Z} / n \mathbb{Z}})\leq g(n)$, where $\gamma$ and $\gamma_t$ denote the domination number and total domination number, respectively, and $g$ is the arithmetic function known as Jacobsthal's function. In particular, we construct integers $n$ with arbitrarily many distinct prime factors such that $\gamma(X_{\mathbb{Z} / n \mathbb{Z}})\leq\gamma_t(X_{\mathbb{Z} / n \mathbb{Z}})\leq g(n)-1$. Extending work of Meki\v{s}, we give lower bounds for the domination numbers of direct products of complete graphs. We also present a simple conjecture for the exact values of the upper domination numbers of direct products of balanced, complete multipartite graphs and prove the conjecture in certain cases. We end with some open problems., Comment: 16 pages, 1 figure

We prove an optimal Zsigmondy bound for elliptic divisibility sequences over function fields in case the $j$-invariant of the elliptic curve is constant. In more detail, given an elliptic curve $E$ with a point $P$ of infinite order, the sequence $D_1$, $D_2, \ldots$ of denominators of multiples $P$, $2P,\ldots$ of $P$ is a strong divisibility sequence in the sense that $\gcd(D_m, D_n) = D_{\gcd(m,n)}$. This is the genus-one analogue of the genus-zero Fibonacci, Lucas and Lehmer sequences. A number $N$ is called a Zsigmondy bound of the sequence if each term $D_{n}$ with $n>N$ presents a new prime factor. The optimal uniform Zsigmondy bound for the genus-zero sequences over $\mathbf{Q}$ is $30$ by Bilu-Hanrot-Voutier, 2000, but finding such a bound remains an open problem in genus one, both over $\mathbf{Q}$ and over function fields. We prove that the optimal Zsigmondy bound for ordinary elliptic divisibility sequences over function fields is $2$ if the $j$-invariant is constant. In the supersingular case, we give a complete classification of which terms can and cannot have a new prime factor., 24 pages

Denote the sum of element orders in a finite group G by ψ ( G ) and let C n denote the cyclic group of order n . Suppose that G is a non-cyclic finite group of order n and q is the least prime divisor of n . We proved that ψ ( G ) ≤ 7 11 ψ ( C n ) and ψ ( G ) 1 q − 1 ψ ( C n ) . The first result is best possible, since for each n = 4 k , k odd, there exists a group G of order n satisfying ψ ( G ) = 7 11 ψ ( C n ) and the second result implies that if G is of odd order, then ψ ( G ) 1 2 ψ ( C n ) . Our results improve the inequality ψ ( G ) ψ ( C n ) obtained by H. Amiri, S.M. Jafarian Amiri and I.M. Isaacs in 2009, as well as other results obtained by S.M. Jafarian Amiri and M. Amiri in 2014 and by R. Shen, G. Chen and C. Wu in 2015. Furthermore, we obtained some ψ ( G ) -based sufficient conditions for the solvability of G .

Finding and constructing Boolean functions with many cryptographic properties to resist a variety of existing attacks are challenging tasks in current cryptography and information security. The key idea in this paper consists of finding a general formula for computing the number of orbits with the same length and Hamming weight by utilizing prime factorization for any integer n greater than 1. Using the property of an orthogonal array to turn the construction of 1-resilient rotation symmetric Boolean functions (RSBFs) on n variables into the solution of a linear system of equations, a complete characterization and a general construction method of this class of functions are also presented. Moreover, a formula for counting the number of functions of this class is found. Not only are the structures of all 1-resilient RSBFs that are obtained more clear, such problems regarding their construction and count are completely and exhaustively solved. In addition, our methods are simpler than existing methods. We provide the exact numbers of 1-resilient RSBFs having ten and 11 variables, which are 162091449508441568747323063140 and 403305984734393392122612918710214418571734777982178890, respectively. Finally, we use three examples to illustrate the application of our methods.

Let θ be a real number such that 0 θ π and cos ⁡ θ ∈ Q . For each positive integer n, we give a parametrization S n ( α ) whose square-free part N n ( α ) for each negative integer α is a θ-congruent number with many prime factors including any given primes (especially, at least n prime factors that are guaranteed to appear) by showing the positivity of the rank of the corresponding θ-congruent number elliptic curve over Q . Especially, we show that if a given odd prime p > 2 n is near 2n, then p appears as a factor of N n ( α ) very often as α varies all over negative integers by proving that the probability of the set of all negative integers α such that p divides N n ( α ) is 2 n + 1 p + 1 .

Given $k, \ell \in {\bf N}^+$, let $x_{i,j}$ be, for $1 \le i \le k$ and $0 \le j \le \ell$, some fixed integers, and define, for every $n \in {\bf N}^+$, $s_n := \sum_{i=1}^k \prod_{j=0}^\ell x_{i,j}^{n^j}$. We prove that the following are equivalent: (a) There are a real $\theta > 1$ and infinitely many indices $n$ for which the number of distinct prime factors of $s_n$ is greater than the super-logarithm of $n$ to base $\theta$. (b) There do not exist non-zero integers $a_0,b_0,\ldots,a_\ell,b_\ell $ such that $s_{2n}=\prod_{i=0}^\ell a_i^{(2n)^i}$ and $s_{2n-1}=\prod_{i=0}^\ell b_i^{(2n-1)^i}$ for all $n$. We will give two different proofs of this result, one based on a theorem of Evertse (yielding, for a fixed finite set of primes $\mathcal S$, an effective bound on the number of non-degenerate solutions of an $\mathcal S$-unit equation in $k$ variables over the rationals) and the other using only elementary methods. As a corollary, we find that, for fixed $c_1, x_1, \ldots,c_k, x_k \in \mathbf N^+$, the number of distinct prime factors of $c_1 x_1^n+\cdots+c_k x_k^n$ is bounded, as $n$ ranges over $\mathbf N^+$, if and only if $x_1=\cdots=x_k$., Comment: 10 pp., no figures. Fixed various mistakes around Lemma 2. To appear in Journal of Number Theory

We study the sum of the $r$th powers of the descent set statistic and how many small prime factors occur in these numbers. Our results depend upon the base $p$ expansion of $n$ and $r$., 14 pages, 1 figure and 2 tables

We improve Irving's method of the double-sieve [7] by using the DHR sieve. By extending the upper and lower bound sieve functions into their respective non-elementary ranges, we are able to make improvements on the previous records on the number of prime factors of irreducible polynomials at prime arguments. In particular, we prove that irreducible quadratics over Z satisfying necessary local conditions are P 4 infinitely often.

There is a large literature on the asymptotic distribution of numbers free of large prime factors, so-called $\textit{smooth}$ or $\textit{friable}$ numbers. But there is very little known about this distribution that is numerically explicit. In this paper we follow the general plan for the saddle point argument of Hildebrand and Tenenbaum, giving explicit and fairly tight intervals in which the true count lies. We give two numerical examples of our method, and with the larger one, our interval is so tight we can exclude the famous Dickman-de Bruijn asymptotic estimate as too small and the Hildebrand-Tenenbaum main term as too large., Comment: 19 pages

In this work, we give upper bounds for n on the title equation. Our results depend on assertions describing the precise exponents of 2 and 3 appearing in the prime factorization of T k ( x ) = ( x + 1 ) k + ( x + 2 ) k + . . . + ( 2 x ) k . Further, on combining Baker's method with the explicit solution of polynomial exponential congruences (see e.g. [6] ), we show that for 2 ≤ x ≤ 13 , k ≥ 1 , y ≥ 2 and n ≥ 3 the title equation has no solutions.

In this paper, we consider the representation of a large positive integer N ≡ 4 ( mod 24 ) in the form p 2 + x 1 2 + x 2 2 + x 3 2 where p is a prime number and x 1 , x 2 , x 3 are almost-primes. A positive integer is called a P r -number if its number of prime factors counted according to multiplicity is at most r. We establish the above representation in the following two different forms. (i) x 1 is a P 2 -number and x 2 x 3 is a P 182 -number; (ii) x 1 x 2 x 3 is a P 12 -number.

Text A positive integer n is called weakly prime-additive if n has at least two distinct prime divisors and there exist distinct prime divisors p 1 , … , p t of n and positive integers α 1 , … , α t such that n = p 1 α 1 + ⋯ + p t α t . It is clear that t ≥ 3 . In 1992, Erdős and Hegyvari proved that, for any prime p, there exist infinitely many weakly prime-additive numbers with t = 3 which are divisible by p. In this paper, we prove that, for any positive integer m, there exist infinitely many weakly prime-additive numbers with t = 3 which are divisible by m if and only if 8 ∤ m . We also present some related results and pose several problems for further research. Video For a video summary of this paper, please visit https://youtu.be/WC_VRFtY07c .

Non-convex quadratically constrained problems frequently appear in chemical engineering when optimizing process networks. Some of these problems can be solved to global optimality by deterministic solvers like BARON and ANTIGONE that mostly use linear programming relaxations coupled with spatial branch and bound. An alternative is to rely on piecewise relaxations, which work by simultaneously partitioning the domain of one variable in every bilinear term and can be significantly tighter, even when setting the number of intervals in the partitions, N , to a small value. In this short note, we generalize the mixed-integer linear programming relaxation formulation from the multiparametric disaggregation technique, to benefit from a logarithmic partitioning scheme in a wide variety of settings. The idea is to select the optimal interval in the partition of a variable by using a mixed-radix numeral system, following the prime factorization of N .

Let N = p q be an RSA modulus with unknown factorization. Some variants of the RSA cryptosystem, such as LUC, RSA with Gaussian primes and RSA type schemes based on singular elliptic curves use a public key e and a private key d satisfying an equation of the form e d − k ( p 2 − 1 ) ( q 2 − 1 ) = 1 . In this paper, we consider the general equation e x − ( p 2 − 1 ) ( q 2 − 1 ) y = z and present a new attack that finds the prime factors p and q in the case that x, y and z satisfy a specific condition. The attack combines the continued fraction algorithm and Coppersmith's technique and can be seen as a generalization of the attacks of Wiener and Blomer–May on RSA.

A signed graph S is a graph in which every edge receive either ‘+’ or ‘-’ called the signs of the edges. The unitary Cayley graph Xn is a graph with vertex set Zn, the integers modulo n, where n is a positive integer greater than 1. Two vertices x1 and x2 are adjacent in the unitary Cayley graph if and only if their difference is in Un, where Un denotes set of all units of the ring Zn. The properties of balancing and clusterability of unitary Cayley meet signed graph S n ∧ are discussed. Apart from this, the canonically consistency of S n ∧ is determined when n has at most two distinct odd prime factors. Sign-compatibility has been worked out for these graphs as well.

In this paper, we show that for any given integer k ≥ 2 , there are infinitely many cube-free integers n having exactly k prime divisors such that n is a sum of two rational cubes. This is a cubic analogue of the work of Tian [Ti] , which proves that there are infinitely many congruent numbers having exactly k prime divisors for any given integer k ≥ 1 .

Let K be an abelian group of order v. A Steiner quadruple system of order v ( SQS ( v ) ) ( K , B ) is called symmetric K-invariant if for each B ∈ B , it holds that B + x ∈ B for each x ∈ K and B = − B + y for some y ∈ K . When the Sylow 2-subgroup of K is cyclic, a necessary and sufficient condition for the existence of a symmetric K-invariant SQS ( v ) was given by Munemasa and Sawa, which is a generalization of a necessary and sufficient condition for the existence of a symmetric cyclic SQS ( v ) shown in Piotrowski's thesis in 1985. In this paper, we prove that a symmetric K-invariant SQS ( v ) exists if and only if v ≡ 2 , 4 ( mod 6 ) , the order of each element of K is not divisible by 8, and there exists a symmetric cyclic SQS ( 2 p ) for any odd prime divisor p of v.

We investigate the structure of nodal solutions for coupled nonlinear Schrodinger equations in the repulsive coupling regime. Among other results, for the following coupled system of N equations, we prove the existence of infinitely many nodal solutions which share the same componentwise-prescribed nodal numbers (0.1) { − Δ u j + λ u j = μ u j 3 + ∑ i ≠ j β u j u i 2 in Ω , u j ∈ H 0 , r 1 ( Ω ) , j = 1 , … , N , where Ω is a radial domain in R n for n = 2 , 3 and a bounded interval for n = 1 , λ > 0 , μ > 0 , and β 0 . More precisely, let p be a prime factor of N and write N = p B . Suppose β ≤ − μ p − 1 . Then for any given non-negative integers P 1 , P 2 , … , P B , (0.1) has infinitely many solutions ( u 1 , … , u N ) such that each of these solutions satisfies the same property: for b = 1 , . . . , B , u p b − p + i changes sign precisely P b times for i = 1 , . . . , p . The result reveals the complex nature of the solution structure in the repulsive coupling regime due to componentwise segregation of solutions. Our method is to combine a heat flow approach as deformation with a minimax construction of the symmetric mountain pass theorem using a Z p group action index. Our method is robust, also allowing to give the existence of one solution without assuming any symmetry of the coupling.

Investigate how to securely outsource the inversion modulo a large composite number.Design the first secure outsourcing algorithm for inversion modulo a large composite number.We can verify the correctness of the result with probability 1.The computation complexity of the client is reduced from O(l3) to O(l2).Provide the formal security definition and the rigorous security proofs. Modular inversion is one of the most basic computations in algorithmic number theory. When it comes to cryptosystems, this computation is very time-consuming since the modulus is generally a large number. It is unrealistic for some devices with limited computation capability (e.g. mobile devices and IC cards) to conduct such a time-consuming computation. In this paper, we investigate how to securely outsource the inversion modulo a large composite number. Based on the Chinese Remainder Theorem (CRT), we design a secure outsourcing algorithm for inversion modulo a large composite number with two known prime factors for the client. Besides the privacy of the number and its modular inversion, our algorithm also protects the privacy of the modulus. We can verify the correctness of the result with probability 1. Traditionally, the complexity of modular inversion for a l-bit modulus is O(l3). By leveraging the cloud, our algorithm reduces the complexity to O(l2) on the client side. Also, we prove the security of our algorithm based on the one-malicious version of two untrusted program model (one-malicious model). We conduct several experiments to demonstrate the validity and the practicality of our proposed algorithm. In appendix, we show that our proposed algorithm can be extended and applied in the secret key generation of RSA algorithm on the resource-constrained devices.

B. Sury proved the following Menon-type identity, ∑ a ∈ U ( Z n ) , b 1 , ⋯ , b r ∈ Z n gcd ⁡ ( a − 1 , b 1 , ⋯ , b r , n ) = φ ( n ) σ r ( n ) , where U ( Z n ) is the group of units of the ring for residual classes modulo n, φ is the Euler's totient function and σ r ( n ) is the sum of r-th powers of positive divisors of n with r being a non-negative integer. Recently, C. Miguel extended this identity from Z to any residually finite Dedekind domain. In this note, we will give a further extension of Miguel's result to the case with many tuples of group of units. For the case of Z , our result reads as follows ∑ a 1 , ⋯ , a s ∈ U ( Z n ) , b 1 , ⋯ , b r ∈ Z n gcd ⁡ ( a 1 − 1 , ⋯ , a s − 1 , b 1 , ⋯ , b r , n ) = φ ( n ) ∏ i = 1 m ( φ ( p i k i ) s − 1 p i k i r − p i k i ( s + r − 1 ) + σ s + r − 1 ( p i k i ) ) , where n = p 1 k 1 ⋯ p m k m is the prime factorization of n.

We define two different simplicial complexes, the common divisor simplicial complex and the prime divisor simplicial complex, from a set of integers, and explore their similarities. We will define a map between the two simplicial complexes, and use this map to show that for any set of integers, the fundamental groups of the resulting simplicial complexes are isomorphic.

A dihedral SQS is an SQS admitting a point-regular dihedral automorphism group. Some constructions of dihedral SQSs are established in this paper. We also prove that for v ≡ 2 , 4 ( m o d 6 ) , there is a dihedral SQS ( v ) if there is a dihedral H ( p , 2 , 4 , 3 ) design or an S -cyclic SQS ( 2 p ) for each odd prime divisor p of v . As a corollary, we enlarge the set of known values of v for which there exists a dihedral SQS ( v ) .

We consider conditions under which L rows of an N point DFT matrix form a matrix with spark L + 1 , i.e. a matrix with full spark. A matrix has spark L + 1 if all L columns are linearly independent. This has application in compressed sensing for MRI and synthetic aperture radar, where measurements are under sampled Fourier measurements, and the observation matrix comprises certain rows of the DFT matrix. It is known that contiguous rows of the DFT matrix render full spark and that from such a base set one can build a suite of other sets of rows that maintain full spark. We consider an alternative base set of the form { 0 , 1 , ? , K } ? { n } , and derive conditions on K, n and the prime factors of N, under which full spark is retained. We show that such a matrix has full spark iff there are no K distinct N-th roots of unity whose n-products form a vanishing sum, and leverage recent characterizations of vanishing sums of N-th roots of unity to establish the stated conditions.

In this note, it is shown that a finite group G is solvable if for each odd prime divisor p of | G | , | Irr ( B 0 ( G ) 2 ) ∩ Irr ( B 0 ( G ) p ) | ≤ 2 , where Irr ( B 0 ( G ) p ) is the set of complex irreducible characters of the principal p-block B 0 ( G ) p of G. Also, the structure of such groups is investigated. Examples show that the bound 2 is best possible.