Asymptotics of the complexity of systems of integer linear forms for additive computations

The computational complexity of integer linear forms is studied. By l ₂(A) we denote the minimal number of the additions and subtractions required for computing the system of p linear forms in q variables x ₁, x ₂, …, x _q that are defined by an integer matrix A of size p × q (repeated use of the results of intermediate computation is permitted). We show that l ₂(A) ? log D(A), where D(A) is the maximum of the absolute values of the minors of A over all minors from order 1 to order min (p, q) (Theorem 1). Moreover, for each sequence of matrices A(n) of size p(n) × q(n) satisfying the condition p + q = o ((log log D(A))^1/2) as n → ∞ the bound l ₂(A) ? log D(A) + o(log D(A)) is valid (Theorem 2). Hence, for all fixed (and even weakly increasing) sizes of matrices that determine a system of integer linear forms, the upper bound on the computational complexity of this system is asymptotically equal to the lower bound.     

Theorems on asymptotics for singular Sturm-Liouville operators with various boundary conditions

We consider the Sturm-Liouville operator L(y) = ?d ² y/dx ² + q(x)y in the space L ₂[0, π], where the potential q(x) is a complex-valued distribution of the first order of singularity; i.e., q(x) = u′(x), u ∈ L ²[0, π]. (Here the derivative is understood in the sense of distributions.) We obtain asymptotic formulas for the eigenvalues and eigenfunctions of the operator in the case of the Neumann-Dirichlet conditions [y ^[1](0) = 0, y(π) = 0] and Neumann conditions [y ^[1](0) = 0, y ^[1](π) = 0] and refine similar formulas for all types of boundary conditions. The leading and second terms of asymptotics are found in closed form.     

Asymptotics of the spectrum of the Sturm-Liouville operator with regular boundary conditions

On the interval (0, π), we consider the spectral problem generated by the Sturm-Liouville operator with regular but not strongly regular boundary conditions. For an arbitrary potential q(x) ∈ L ₁ (0, π) [q(x) ∈ L ₂(0, π)], we establish exact asymptotic formulas for the eigenvalues of this problem.     

On exponential sums over primes and application in Waring-Goldbach problem

In this paper, we prove the following estimate on exponential sums over primes: Let κ≥1,βκ=1/2 log κ/log2, x≥2 and α=a/q λsubject to (a, q) = 1, 1≤a≤q, and λ∈R. Then As an application, we prove that with at most O(N2/8 ε) exceptions, all positive integers up to N satisfying some necessary congruence conditions are the sum of three squares of primes. This result is as strong as what has previously been established under the generalized Riemann hypothesis.     

A duality between locally compact groups and certain Banach algebras

We make precise the following statements: B(G), the Fourier-Stieltjes algebra of locally compact group G, is a dual of G and vice versa. Similarly, A(G), the Fourier algebra of G, is a dual of G and vice versa. We define an abstract Fourier (respectively, Fourier-Stieltjes) algebra; we define the dual group of such a Fourier (respectively, Fourier-Stieltjes) algebra; and we prove the analog of the Pontriagin duality theorem in this context. The key idea in the proof is the characterization of translations of B(G) as precisely those isometric automorphisms Φ of B(G) which satisfy ∥ p ? e^iθΦp ∥² + ∥ p + e^iθΦp ∥² = 4 for all θ ∈ $\text{R}$ and all pure positive definite functions p with norm one. One particularly interesting technical result appears, namely, given x₁, x₂?G, neither of which is the identity e of G, then there exists a continuous, irreducible unitary representation π of G (which may be chosen from the reduced dual of G) such that π(x₁) ≠ π(e) and π(x₂) ≠ π(e). We also note that the group of isometric automorphisms of B(G) (or A(G)) contains as a (“large”) ^.closed, normal subgroup the topological version of Burnside's “holomorph of G.”     

On integers which are the sum of a power of 2 and a polynomial value

Here, we show that if f (x) ∈ ?[x] has degree at least 2 then the set of integers which are of the form 2 ^k + f (m) for some integers k ≥ 0 and m is of asymptotic density 0. We also make some conjectures and prove some results about integers not of the form |2 ^k ± m ^a (m ? 1)|.     

On Templeman averages and variation functions

Let S be a countable semigroup acting in a measure-preserving fashion (g ? T _g ) on a measure space (Ω, A, µ). For a finite subset A of S, let |A| denote its cardinality. Let (A _k ) _k=1 ^∞ be a sequence of subsets of S satisfying conditions related to those in the ergodic theorem for semi-group actions of A. A. Tempelman. For A-measureable functions f on the measure space (Ω, A, μ) we form for k ≥ 1 the Templeman averages \(\pi _k (f)(x) = \left| {A_k } \right|^{ - 1} \sum\nolimits_{g \in A_k } {T_g f(x)}\) and set V _q f(x) = (Σ _k≥1|π _k+1(f)(x) ? π _k (f)(x)|q)^1/q when q ∈ (1, 2]. We show that there exists C > 0 such that for all f in L ¹(Ω, A, µ) we have µ({x ∈ Ω: V _q f(x) > λ}) ≤ C(∫_Ω | f | dµ/λ). Finally, some concrete examples are constructed.     

Chen’s Conjecture and Its Generalization

Let l1, l2, ..., lg be even integers and x be a sufficiently large number. In this paper, the authors prove that the number of positive odd integers k ≤ x such that （k ＋l1）^2, （k ＋l2）^2, ..., （k ＋lg）^2 can not be expressed as 2^n＋p^α is at least c（g）x, where p is an odd prime and the constant c（g） depends only on g.     

Congruent elliptic curves with non-trivial Shafarevich-Tate groups: Distribution part

Given a large positive number x and a positive integer k, we denote by Qk(x) the set of congruent elliptic curves E(n): y2= z3- n2 z with positive square-free integers n x congruent to one modulo eight,having k prime factors and each prime factor congruent to one modulo four. We obtain the asymptotic formula for the number of congruent elliptic curves E(n)∈ Qk(x) with Mordell-Weil ranks zero and 2-primary part of Shafarevich-Tate groups isomorphic to(Z/2Z)2. We also get a lower bound for the number of E(n)∈ Qk(x)with Mordell-Weil ranks zero and 2-primary part of Shafarevich-Tate groups isomorphic to(Z/2Z)4. The key ingredient of the proof of these results is an independence property of residue symbols. This property roughly says that the number of positive square-free integers n x with k prime factors and residue symbols(quadratic and quartic) among its prime factors being given compatible values does not depend on the actual values.     

Universally bad integers and the 2-adics

In his 1964 paper, de Bruijn (Math. Comp. 18 (1964) 537) called a pair (a,b) of positive odd integers good, if , where is the set of nonnegative integers whose 4-adic expansion has only 0's and 1's, otherwise he called the pair (a,b) bad. Using the 2-adic integers we obtain a characterization of all bad pairs. A positive odd integer u is universally bad if (ua,b) is bad for all pairs of positive odd integers a and b. De Bruijn showed that all positive integers of the form u=2^k+1 are universally bad. We apply our characterization of bad pairs to give another proof of this result of de Bruijn, and to show that all integers of the form u=φ_p^k(4) are universally bad, where p is prime and φ_n(x) is the nth cyclotomic polynomial. We consider a new class of integers we call de Bruijn universally bad integers and obtain a characterization of such positive integers. We apply this characterization to show that the universally bad integers u=φ_p^k(4) are in fact de Bruijn universally bad for all primes p>2. Furthermore, we show that the universally bad integers φ_2^k(4), and more generally, those of the form 4^k+1, are not de Bruijn universally bad.     

The asymptotic number of labeled connected graphs with a given number of vertices and edges

Let c(n, q) be the number of connected labeled graphs with n vertices and q ≤ N = (2n ) edges. Let x = q/n and k = q ? n. We determine functions w_k ? 1. a(x) and φ(x) such that c(n, q) ? w_k(q^N)eⁿφ(x)+a(x) uniformly for all n and q ≥ n. If ? > 0 is fixed, n→ ∞ and 4q > (1 + ?)n log n, this formula simplifies to c(n, q) ? (N^q) exp(–ne^?2q/n). on the other hand, if k = o(n^1/2), this formula simplifies to c(n, n + k) ? 1/2 w_k (3/π)^1/2 (e/12k)^k/2nⁿ?^(3k?1)/2.     

More coverings by rook domains

The set V_kⁿ of all n-tuples (x₁, x₂,…, x_n) with x_i?, $\text{Z}$_k is considered. The problem treated in this paper is determining σ(n, k), the minimum size of a set W ? V_kⁿ such that for each x in V_kⁿ, there is an element in W that differs from x in at most one coordinate. By using a new constructive method, it is shown that σ(n, p) ? (p ? t + 1)p^n?r, where p is a prime and $\text{n = 1 +}\text{t(p}{}^{\mathrm{r?1}}\text{? 1)}\text{(p ? 1)}$ for some integers t and r. The same method also gives σ(7, 3) ? 216. Another construction gives the inequality σ(n, kt) ? σ(n, k)t^n?1 which implies that σ(q + 1, qt) = q^q?1t^q when q is a prime power. By proving another inequality σ(np + 1, p) ? σ(n, p)p^n(p?1), σ(10, 3) ? 5 · 3⁶ and σ(16, 5) ? 13 · 5¹² are obtained.     

The Erdös-Kac theorem for additive arithmetical semigroups

We show that the Erdös-Kac theorem for additive arithmetical semigroups can be proved under the condition that the counting function of elements has the asymptotics G(n) = q ⁿ (A + O(1/(lnn)^k) as n → ∞ with A > 0, q > 1, and arbitrary k ∈ ? and that P(n) = O(q ⁿ /n) for the number of prime elements of degree n. This improves a result of Zhang.     

Copositive pointwise approximation

We prove that if a functionf ∈C ⁽¹⁾ (I),I: = [?1, 1], changes its signs times (s ∈ ?) within the intervalI, then, for everyn > C, whereC is a constant which depends only on the set of points at which the function changes its sign, andk ∈ ?, there exists an algebraic polynomialP _n =P _n (x) of degree ≤n which locally inherits the sign off(x) and satisfies the inequality $$\left| {f\left( x \right) - P_n \left( x \right)} \right| \leqslant c\left( {s,k} \right)\left( {\frac{1}{{n^2 }} + \frac{{\sqrt {1 - x^2 } }}{n}} \right)\omega _k \left( {f'; \frac{1}{{n^2 }} + \frac{{\sqrt {1 - x^2 } }}{n}} \right), x \in I$$ , where ω _k (f′;t) is thekth modulus of continuity of the functionf’. It is also shown that iff ∈C (I) andf(x) ≥ 0,x ∈I then, for anyn ≥k ? 1, there exists a polynomialP _n =P _n (x) of degree ≤n such thatP _n (x) ≥ 0,x ∈I, and |f(x) ?P _n (x)| ≤c(k)ω _k (f;n ^?2 +n ^?1 √1 ?x ²),x ∈I.     

On the Sylow graph of a group and Sylow normalizers

Let G be a finite group and G _p be a Sylow p-subgroup of G for a prime p in π(G), the set of all prime divisors of the order of G. The automiser A _p (G) is defined to be the group N _G (G _p )/G _p C _G (G _p ). We define the Sylow graph Γ _A (G) of the group G, with set of vertices π(G), as follows: Two vertices p, q ∈ π(G) form an edge of Γ _A (G) if either q ∈ π(A _p (G)) or p ∈ π(A _q (G)). The following result is obtained Theorem: Let G be a finite almost simple group. Then the graph Γ _A (G) is connected and has diameter at most 5. We also show how this result can be applied to derive information on the structure of a group from the normalizers of its Sylow subgroups.     

On the class of limits of lacunary trigonometric series

Let (n _k ) _k≧1 be a lacunary sequence of positive integers, i.e. a sequence satisfying n _k+1/n _k > q > 1, k ≧ 1, and let f be a “nice” 1-periodic function with ∝ ₀ ¹ f(x) dx = 0. Then the probabilistic behavior of the system (f(n _k x)) _k≧1 is very similar to the behavior of sequences of i.i.d. random variables. For example, Erd?s and Gál proved in 1955 the following law of the iterated logarithm (LIL) for f(x) = cos 2πx and lacunary $ (n_k )_{k \geqq 1} $ : (1) $$ \mathop {\lim \sup }\limits_{N \to \infty } (2N\log \log N)^{1/2} \sum\limits_{k = 1}^N {f(n_k x)} = \left\| f \right\|_2 $$ for almost all x ∈ (0, 1), where ‖f‖₂ = (∝ ₀ ¹ f(x)² dx)^1/2 is the standard deviation of the random variables f(n _k x). If (n _k ) _k≧1 has certain number-theoretic properties (e.g. n _k+1/n _k → ∞), a similar LIL holds for a large class of functions f, and the constant on the right-hand side is always ‖f‖₂. For general lacunary (n _k ) _k≧1 this is not necessarily true: Erd?s and Fortet constructed an example of a trigonometric polynomial f and a lacunary sequence (n _k ) _k≧1, such that the lim sup in the LIL (1) is not equal to ‖f‖₂ and not even a constant a.e. In this paper we show that the class of possible functions on the right-hand side of (1) can be very large: we give an example of a trigonometric polynomial f such that for any function g(x) with sufficiently small Fourier coefficients there exists a lacunary sequence (n _k ) _k≧1 such that (1) holds with √‖f‖ ₂ ² + g(x) instead of ‖f‖₂ on the right-hand side.     

Approximate Solution to Inverse Scattering Problem for Potentials With Small Support

Let q(x) be a real-valued function with compact support D⊂ℝ³. Given the scattering amplitude A(α′, α, k) for all α′, α∈S² and a fixed frequency k>0, the moments of q(x) up to the second order are found using a computationally simple and relatively stable two-step procedure. First, one finds the zeroth moment (total intensity) and the first moment (centre of inertia) of the potential q. Second, one refines the above moments and finds the tensor of the second central moments of q. Asymptotic error estimates are given for these moments as d = diam(D)→0. Physically, this means that (k²+sup∣q(x))d²<1 and sup∣q(x)∣d<k. The found moments give an approximate position and the shape of the support of q. In particular, an ellipsoid D̃ and a real constant q̃ are found, such that the potential q̃ (x) = q̃, x∈D̃, and q̃ (x) = 0, x∉ D̃, produces the scattering data which fit best the observed scattering data and has the same zeroth, first, and second moments as the desired potential. A similar algorithm for finding the shape of D given only the modulus of the scattering amplitude A(α′,α) is also developed.     

Average running time of the fast Fourier transform

We compare several algorithms for computing the discrete Fourier transform of n numbers. The number of “operations” of the original Cooley-Tukey algorithm is approximately 2nA(n), where A(n) is the sum of the prime divisors of n. We show that the average number of operations satisfies $\text{1}\text{x}\text{)∑}{}_{\mathrm{n\le x}}\text{2n A(n) ～ (}\text{π}{}^2\text{9}\text{)(}\text{x}{}^2\text{log}\text{x}\text{)}$. The average is not a good indication of the number of operations. For example, it is shown that for about half of the integers n less than x, the number of “operations” is less than n^1.61. A similar analysis is given for Good's algorithm and for two algorithms that compute the discrete Fourier transform in O(n log n) operations: the chirp-z transform and the mixed-radix algorithm that computes the transform of a series of prime length p in O(p log p) operations.     

On the completeness of the system of root vectors of the Sturm-Liouville operator with general boundary conditions

We study general boundary value problems with nondegenerate characteristic determinant Δ(λ) for the Sturm-Liouville equation on the interval [0, 1]. Necessary and sufficient conditions for the completeness of root vectors are obtained in terms of the potential. In particular, it is shown that if Δ(λ) ≠ const, q(·) ∈ C ^k [0, 1] for some k ? 0, and q ^(k)(0) ≠ (?1) ^k q ^(k)(1), then the system of root vectors is complete and minimal in L ^p [0, 1] for p ∈ [1,∞).