On the parity of the partition function

Let N be the set of all positive integers and D a subset of N. Let p(D,n) be the number of partitions of n with parts in D and let |D(x)| denote the number of elements of D not exceeding x. It is proved that if D is an infinite subset of N such that p(D,n) is even for all n?n₀, then |D(x)|?logx/log2−logn₀/log2. Moreover, if D is an infinite subset of N such that p(D,n) is odd for all n?n₀ and , then |D(x)|?logx/log2−logn₀/log2. These lower bounds are essentially the best possible.     

Romanoff theorem in a sparse set

Let A be any subset of positive integers,and P the set of all positive primes.Two of our results are:(a) the number of positive integers which are less than x and can be represented as 2k + p(resp.p-2k) with k ∈ A and p ∈ P is more than 0.03A(log x/log 2)π(x) for all sufficiently large x;(b) the number of positive integers which are less than x and can be represented as 2q + p with p,q ∈ P is(1 + o(1))π(log x/log 2)π(x).Four related open problems and one conjecture are posed.     

A specific family of cyclotomic polynomials of order three

Let A(n) be the largest absolute value of any coefficient of n-th cyclotomic polynomial Φn(x).We say Φn(x) is flat if A(n) = 1.In this paper,for odd primes p q r and 2r ≡ 1(mod pq),we prove that Φpqr(x) is flat if and only if p = 3 and q ≡ 1(mod 3).     

ADDITIVE FAMILIES OF INVARIANTS OF FORMS OF DEGREE d

Abstract

Let d be a positive integer, and F be a field of characteristic zero. Suppose that for each positive integer n, I _n, is a GL _n,(F)- invariant of forms of degree d in x₁, …, x _n, over F. We call {I _n} an additive family of invariants if I _p+q (f ⊥ g) = I _p(f).I _q(g) whenever f; g are forms of degree d over F in x _l, …, x _p; …, x _q respectively, and where (f ⊥ g)(x _l, …, x _p+q) = f(x ₁, …, x _p,) + g (x _p+1, …, x _p+q). It is well-known that the family of discriminants of the quadratic forms is additive. We prove that in odd degree d each invariant in an additive family must be a constant. We also give an example in each even degree d of a nontrivial family of invariants of the forms of degree d. The proofs depend on the symbolic method for representing invariants of a form, which we review.     

Asymptotic estimates of sums involving the Moebius function

Let p(n) denote the smallest prime factor of an integer n>1 and let p(1)=∞. We study the asymptotic behavior of the sum M(x,y)=Σ_{1≤n≤x,p(n)>y}μ(n) and use this to estimate the size of A(x)=max_|f|≤1|Σ_2≤n<xμ(n)f(p(n))|, where μ(n) is the Moebius function. Applications of bounds for A(x), M(x,y) and similar quantities are discussed.     

An application of L-functions of imaginary quadratic fields

Let F₁(x, y),…, F_2h+1(x, y) be the representatives of equivalent classes of positive definite binary quadratic forms of discriminant ?q (q is a prime such that q ≡ 3 mod 4) with integer coefficients, then the number of integer solutions of F_i(x, y) = n (i = 1,…, 2h + 1) can be calculated for each natural number n using L-functions of imaginary quadratic field $\text{Q}$((?q)^1/2).     

On the enumeration of certain weighted graphs

We enumerate weighted simple graphs with a natural upper bound condition on the sum of the weight of adjacent vertices. We also compute the generating function of the numbers of these graphs, and prove that it is a rational function. In particular, we show that the generating function for connected bipartite simple graphs is of the form p₁(x)/(1-x)^m+1. For nonbipartite simple graphs, we get a generating function of the form p₂(x)/(1-x)^m+1(1+x)^l. Here m is the number of vertices of the graph, p₁(x) is a symmetric polynomial of degree at most m, p₂(x) is a polynomial of degree at most m+l, and l is a nonnegative integer. In addition, we give computational results for various graphs.     

Binary Segmentation for Multivariate Polynomials

This paper develops a fast method of binary segmentation for multivariate integer polynomials and applies it to polynomial multiplication, pseudodivision, resultant and gcd calculations. In the univariate case, binary segmentation yields the fastest known method for multiplication of integer polynomials, even slightly faster than fast Fourier transform methods (however, the underlying fast integer multiplication method is based on fast Fourier transforms). Fischer and Paterson ("SIAM-AMS Proceedings, 1974," pp. 113-125) seem to be the first authors who suggest binary segmentation for polynomials with coefficients in {0, 1}. Schönhage (J. Complexity1 (1985), 118-137), as well as Bini and Pan (J. Complexity2 (1986), 179-203) have applied the binary segmentation to univariate polynomial division and gcd calculation. In the multivariate case, well- known methods are the iterated application of univariate binary segmentation and Kronecker′s map. Our method of binary segmentation to the contrary is based on a one-step algebra homomorphism mapping multivariate polynomials directly into integers. More precisely, the variables x₁, . . . , x_n of a multivariate polynomial are substituted by integers 2^ν₁, . . . , 2^ν_n, where ν₁ < · · · < ν_n are chosen as small as possible. If n is the number of variables, d bounds the total degrees, and l bounds the bit lengths of the input, we achieve the bit complexities O(ψ((2d)ⁿ (n log d + l))) for multivariate multiplication, O(d ψ(d²ⁿ(n log d + l))) for multivariate pseudo-division (provided n = O(d log d)), and O(d ψ((2d²)ⁿ (n log d + l))) for multivariate subresultant chain calculation. Here ψ(l) = l log l log log l denotes the complexity of integer multiplication.     

The least common multiple of a sequence of products of linear polynomials

Let f(x) be the product of several linear polynomials with integer coefficients. In this paper, we obtain the estimate log?lcm?(f(1),…,f(n))～An as n→∞, where A is a constant depending on?f.     

On the Comparison of Cryptographical Properties of Two Different Families of Graphs with Large Cycle Indicator

The paper is devoted to the implementations of the public key algorithms based on simple algebraic graphs A(n, K) and D(n, K) defined over the same finite commutative ring K. If K is a finite field both families are families of graphs with large cycle indicator. In fact, the family D(n, F _q ) is a family of graphs of large girth (f.g.l.g.) with c =?1, their connected components CD(n, F _q ) form the f.g.l.g. with the speed of growth 4/3. Family A(n, q), char F _q ?? 2 is a family of connected graphs with large cycle indicator with the largest possible speed of growth. The computer simulation demonstrates the advantage (better density which is the number of monomial expressions) of public rules derived from A(n, q) in comparison with symbolic algorithm based on graphs D(n, q).     

A note on approximation properties of q-Durrmeyer operators

In this paper, the approximation properties of q-Durrmeyer operators D_n,q(f;x) for f∈C[0,1] are discussed. The exact class of continuous functions satisfying approximation process lim_n→∞D_n,q(f;x)=f(x) is determined. The results of the paper provide an elaboration of the previously-known ones on operators D_n,q.     

A note on the number of solutions of the generalized Ramanujan-Nagell equation x 2 ? D = p n

Let D be a positive integer, and let p be an odd prime with p ? D. In this paper we use a result on the rational approximation of quadratic irrationals due to M. Bauer, M.A. Bennett: Applications of the hypergeometric method to the generalized Ramanujan-Nagell equation. Ramanujan J. 6 (2002), 209–270, give a better upper bound for N(D, p), and also prove that if the equation U ² ? DV ² = ?1 has integer solutions (U, V), the least solution (u ₁, v ₁) of the equation u ² ? pv ² = 1 satisfies p ? v ₁, and D > C(p), where C(p) is an effectively computable constant only depending on p, then the equation x ² ? D = p ⁿ has at most two positive integer solutions (x, n). In particular, we have C(3) = 10⁷.     

The weight distribution of irreducible cyclic codes with block lengths n1((q1−1)N)

We study the weight distribution of irreducible cyclic (n, k) codeswith block lengths n = n₁((q¹ ? 1)/N), where N|q ? 1, gcd(n₁,N) = 1, and gcd(l,N) = 1. We present the weight enumerator polynomial, A(z), when k = n₁l, k = (n₁ ? 1)l, and k = 2l. We also show how to find A(z) in general by studying the generator matrix of an (n₁, m) linear code, $\text{V}{}^1{}_{\mathrm{d}}$ over GF(q^d) where d = gcd (ord_n1(q), l). Specifically we study A(z) when $\text{V}{}^1{}_{\mathrm{d}}$ is a maximum distance separable code, a maximal shiftregister code, and a semiprimitive code. We tabulate some numbers A_μ which completely determine the weight distributionof any irreducible cyclic (n₁(2¹ ? 1), k) code over GF(2) for all n₁ ? 17.     

Polynomials and primitive roots in finite fields

The primitive elements of a finite field are those elements of the field that generate the multiplicative group of k. If f(x) is a polynomial over k of small degree compared to the size of k, then f(x) represents at least one primitive element of k. Also f(x) represents an lth power at a primitive element of k, if l is also small. As a consequence of this, the following results holds.Theorem. Let g(x) be a square-free polynomial with integer coefficients. For all but finitely many prime numbers p, there is an integer a such that g(a) is equivalent to a primitive element modulo p.Theorem. Let l be a fixed prime number and f(x) be a square-free polynomial with integer coefficients with a non-zero constant term. For all but finitely many primes p, there exist integers a and b such that a is a primitive element and f(a) ≡ b¹ modulo p.     

Bilinear Relative Equilibria of Identical Point Vortices

A new class of bilinear relative equilibria of identical point vortices in which the vortices are constrained to be on two perpendicular lines, conveniently taken to be the x- and y-axes of a Cartesian coordinate system, is introduced and studied. In the general problem we have m vortices on the y-axis and n on the x-axis. We define generating polynomials q(z) and p(z), respectively, for each set of vortices. A second-order, linear ODE for p(z) given q(z) is derived. Several results relating the general solution of the ODE to relative equilibrium configurations are established. Our strongest result, obtained using Sturm’s comparison theorem, is that if p(z) satisfies the ODE for a given q(z) with its imaginary zeros symmetric relative to the x-axis, then it must have at least n?m+2 simple, real zeros. For m=2 this provides a complete characterization of all zeros, and we study this case in some detail. In particular, we show that, given q(z)=z ²+η ², where η is real, there is a unique p(z) of degree n, and a unique value of η ²=A _n , such that the zeros of q(z) and p(z) form a relative equilibrium of n+2 point vortices. We show that $A_{n} \approx\frac{2}{3}n + \frac{1}{2}$ , as n→∞, where the coefficient of n is determined analytically, the next-order term numerically. The paper includes extensive numerical documentation on this family of relative equilibria.     

A criterion for generating full matrix algebras

Let M_n(F) be the algebra of n×n matrices over a field F, and let A∈M_n(F) have characteristic polynomial c(x)=p₁(x)p₂(x)?p_r(x) where p₁(x),…,p_r(x) are distinct and irreducible in F[x]. Let X be a subalgebra of M_n(F) containing A. Under a mild hypothesis on the p_i(x), we find a necessary and sufficient condition for X to be M_n(F).     

Oscillation and nonoscillation of nonlinear second order difference equations

In this paper, we study oscillation and nonoscillation behaviour of the second order nonlinear difference equations of the form $$\Delta (r_n \psi (x_n )\Delta x_n ) + q_{n + 1} f(x_{n + 1} ) = 0, n \in N(n_o ),$$ and $$\Delta (r_n \psi (x_n )\Delta x_n ) + q_n f(n,x_n ) = 0, n \in N(n_o ),$$ whereN(n _o ) =n _o ,n _o + 1, …, (n _o is a fixed nonnegative integer number), Δx_n =x _n +1?x _n is the forward difference operator,x :N(n _o ) → ?,r :N(n _o ) → (0, ∞), Ψ : ? → (0, ∞),f is a real valued continuous function, andq _n is a sequence of real valued.     

Probabilistic computation of integer polynomial GCDs

We describe a probabilistic algorithm for the computation of the gcd of two univariate integer polynomials of degrees ≤ n with their l¹-norms being bounded by 2^h and estimate its expected running time by a worst-case bound of O(n(n + h)^{1 + o(1)}) bit operations.