A congruence involving products of q-binomial coefficients

In this paper we establish a q-analogue of a congruence of Sun concerning the products of binomial coefficients modulo the square of a prime.     

On the value set of the Ramanujan function

We give lower bounds on the number of distinct values of the Ramanujan function τ(n), n ≦ x, and on the number of distinct residues of τ(n), n ≦ x, modulo a prime ℓ. We also show that for any prime ℓ the values τ(n), n ≦ ℓ⁴, form a finite additive basis modulo ℓ. Received: 6 October 2004     

Character Sums in Short Intervals and the Multiplication Table Modulo a Large Prime

We obtain nontrivial estimates of character sums over short intervals for almost all moduli. These bounds and the method of Karatsuba for solving multiplicative ternary problems are used to prove that for π(X)(1 + o(1)) primes p,p ≤ X, there are p(1 + o(1)) residue classes modulo p of the form xy (mod p), where 1 ≤ x, y ≤ p^?(log p)^1,087. We also prove that for any prime p there are p(1 + o(1)) residue classes modulo p of the form xy^* (mod p), where 1 ≤ x, y ≤ p^?(log p)^1+o(1) and y^* is defined by yy^* ≡ 1 (mod p).     

Congruence properties of the coefficients of the Drinfeld modular invariant

 Let be the expansion at infinity of the Drinfeld modular invariant. We know that the coefficients c _n 's are in the polynomial ring 𝔽_q[T]. In this text, we prove for these coefficients congruence properties modulo powers of p, where p  𝔽 _q [T] is a polynomial of degree 1. Received: 19 April 2002 Mathematics Subject Classification (2000): 11F52, 11F33, 11G09     

An O(n 2) active set algorithm for the solution of a parametric quadratic program

In this paper, an O(n ²) active set method is presented for minimizing the parametric quadratic function (1/2)x′Dx-a′x + λmax(c - γ x,0) subject to l ⩽ x ⩽ b, for all nonnegative values of the parameter γ. Here, D is a positive diagonal n x n matrix, a and γ are arbitrary N-vectors, c is an arbitrary scalar, l and b are arbitrary n-vectors, such thatl ⩽ b. An extension of this algorithm is presented for minimizing the parametric function (1/2)x′Dx-a ^′ x + λ |γ′x - c| subject to l ⩽ x ⩽ b. It is also shown that these problems arise naturally in a tax programming problem. This revised version was published online in August 2006 with corrections to the Cover Date.     

A remark on the least n with χ (n) ≠ 1

Suppose that a > 2. We prove that the number of positive integers q ≦ Q such that there exists a primitive character χ modulo q with χ (n) = 1 for all n ≦ (log Q)^a is O(Q^1/(1-a)+ε). Received: 7 December 2004     

A class of problems for which cyclic relaxation converges linearly

The method of cyclic relaxation for the minimization of a function depending on several variables cyclically updates the value of each of the variables to its optimum subject to the condition that the remaining variables are fixed. We present a simple and transparent proof for the fact that cyclic relaxation converges linearly to an optimum solution when applied to the minimization of functions of the form for a _i,j ,b _i ,c _i ∈ℝ_≥0 with max {min {b ₁,b ₂,…,b _n },min {c ₁,c ₂,…,c _n }}>0 over the n-dimensional interval [l ₁,u ₁]×[l ₂,u ₂]×⋅⋅⋅×[l _n ,u _n ] with 0<l _i <u _i for 1≤i≤n. Our result generalizes several convergence results that have been observed for algorithms applied to gate- and wire-sizing problems that arise in chip design.     

On the algebraic independence in the selberg class

We prove that a functionF of the Selberg class ℐ is ab-th power in ℐ, i.e.,F=H ^b for someHσ ℐ, if and only ifb divides the order of every zero ofF and of everyp-componentF _p. This implies that the equationF ^a=G^b with (a, b)=1 has the unique solutionF=H ^b andG=H ^a in ℐ. As a consequence, we prove that ifF andG are distinct primitive elements of ℐ, then the transcendence degree of ℂ[F,G] over ℂ is two.     

Bounding the Derived Length for a Given Set of Character Degrees

Let G be a finite solvable group with {1, a, b, c, ab, ac} as the character degree set, where a ,b, and c are pairwise coprime integers greater than 1. We show that the derived length of G is at most 4. This verifies that the Taketa inequality, dl(G) ≤ |cd(G)|, is valid for solvable groups with {1, a, b, c, ab, ac} as the character degree set. Also, as a corollary, we conclude that if a, b, c, and d are pairwise coprime integers greater than 1 and G is a solvable group such that cd(G) = {1, a, b, c, d, ac, ad, bc, bd}, then dl(G) ≤ 5. Finally, we construct a family of solvable groups whose derived lengths are 4 and character degree sets are in the form {1, p, b, pb, q ^p , pq ^p }, where p is a prime, q is a prime power of an odd prime, and b > 1 is integer such that p, q, and b are pairwise coprime. Hence, the bound 4 is the best bound for the derived length of solvable groups whose character degree set is in the form {1, a, b, c, ab, ac} for some pairwise coprime integers a, b, and c.     

On the Existence of Specific Stars in Planar Graphs

Given a graph G, a (k;a,b,c)-star in G is a subgraph isomorphic to a star K_1,3 with a central vertex of degree k and three leaves of degrees a, b and c in G. The main result of the paper is: Every planar graph G of minimum degree at least 3 contains a (k;a,b,c)-star with a≤ b≤ c and (i) k = 3, a≤ 10, or (ii) k = 4, a = 4, 4≤ b≤ 10, or (iii) k = 4, a = 5, 5≤ b≤ 9, or (iv) k = 4, 6≤ a≤ 7, 6≤ b≤ 8, or (v) k = 5, 4≤ a≤ 5, 5≤ b≤ 6 and 5≤ c≤ 7, or (vi) k = 5 and a = b = c = 6.     

On the Hausdorff dimensions of certain attractors

For any a,b∈R let ϕ_a,b(x)=ax+b(x∈R). Suppose 0<a<1. Let C_a,b be the generalized a-Cantor set with generating iterated function systme {ϕ_a,0, ϕ_a,b; ϕ_a,l}. Then we prove the Hausdorff dimension of C_a,c² C_{a,c^2 } is \fracln(3 - ?5 - ln2lna\frac{{ln(3 - \sqrt 5 - ln2}}{{lna}} when 0<a≤2 cos 80°.     

On a substitution subshift related to the Grigorchuk group

We study the dynamics of a substitution subshift given by the substitution a → aca, b → d, c → b, d → c, which is related to the Grigorchuk group. This dynamical system is shown to be, up to a countable set, conjugate to the binary odometer.     

Explicit generalized zolotarev polynomials with complex coefficients

We give explicitly a class of polynomials with complex coefficients of degreen which deviate least from zero on [−1, 1] with respect to the max-norm among all polynomials which have the same,m + 1, 2m ≤n, first leading coefficients. Form=1, we obtain the polynomials discovered by Freund and Ruschewyh. Furthermore, corresponding results are obtained with respect to weight functions of the type 1/√ρl, whereρl is a polynomial positive on [−1, 1].     

Square-free orders for CM elliptic curves modulo <Emphasis Type="Italic">p</Emphasis>

Let E be an elliptic curve defined over , of conductor N, and with complex multiplication. We prove unconditional and conditional asymptotic formulae for the number of ordinary primes , p ≤ x, for which the group of points of the reduction of E modulo p has square-free order. These results are related to the problem of finding an asymptotic formula for the number of primes p for which the group of points of E modulo p is cyclic, first studied by Serre (1977). They are also related to the stronger problem about primitive points on E modulo p, formulated by Lang and Trotter (Bull Am Math Soc 83:289–292, 1977), and the one about the primality of the order of E modulo p, formulated by Koblitz [Pacific J. Math. 131(1):157–165, 1988].     

On the solutions of a boundary value problem arising in free convection with prescribed heat flux

For given , c < 0, we are concerned with the solution f _b of the differential equation f ′′′ + ff ′′ + g(f ′) = 0 satisfying the initial conditions f(0) = a, f ′ (0) = b, f ′′ (0) = c, where g is some nonnegative subquadratic locally Lipschitz function. It is proven that there exists b _* > 0 such that f _b exists on [0, + ∞) and is such that as t → + ∞, if and only if b ≥ b _*. This allows to answer questions about existence, uniqueness and boundedness of solutions to a boundary value problem arising in fluid mechanics, and especially in boundary layer theory.      

Digital Expansions with Respect to Different Bases

We consider the g-ary expansion N=∑ _k b _k (N, g)g ^k of non-negative integers N and prove various results on the distribution and the mean value of the k-th digit b _k (N, g) if g varies in an interval of the form 2≤g≤N ^η. As an application we also consider the average value of the sum-of-digits function s(N, g)=∑ _k b _k (N, g). Received 5 November 2001 RID="a" ID="a" Dedicated to Professor Edmund Hlawka on the occasion of his 85th birthday     

Stabilization of flows through porous media

In this article, we study the motion of an incompressible homogeneous Newtonian fluid in a rigid porous medium of infinite extent. The fluid is bounded below by a fixed layer having an external source (with an injection rate b), and above by a free surface moving under the influence of gravity. The flow is governed by Darcy’s law. If b(c) = 0 for some c > 0 then the system admits (u, f) ≡ (c, c) as an equilibrium solution. We shall prove that the stability properties of this equilibrium are determined by the slope of b in c : The equilibrium is unstable if b′(c) < 0, whereas b′(c) > 0 implies exponential stability. Zhaoyong Feng: He is grateful to the DFG for financial support through the Graduiertenkolleg 615 “Interaction of Modeling, Computation Methods and Software Concepts for Scientific-Technological Problems”.     

Complexity bound for the absolute factorization of parametric polynomials

An algorithm is constructed for the absolute factorization of polynomials with algebraically independent parametric coefficients. It divides the parameter space into pairwise disjoint pieces such that the absolute factorization of polynomials with coefficients in each piece is given uniformly. Namely, for each piece there exist a positive integer l ≤ d, l variables C₁, ..., C_l algebraically independent over the ground field F, and rational functions b_J,j of the parameters and of the variables C₁, ..., C_l such that for any parametric polynomial f with coefficients in this piece, there exist c₁, ..., with f = Π _j G _j where G _j = Σ_|J| B _J,j Z ^J is absolutely irreducible. Here Z = (Z₀, ..., Z_n) are the variables of f, each B_J,j is the value of b_J,j at the coefficients of f and c₁, ..., c_l, and denotes the algebraic closure of F. The number of pieces does not exceed (2d²+1)^2n+3d+5, and the algorithm performs arithmetic operations in F (thus the number of operations is exponential in the number r = ( _n+1 ^n+1+d ) of coefficients of f), and its binary complexity is bounded by if F = ℚ and by if , where d is an upper bound on the degrees of polynomials. The techniques used include the Hensel lemma and the quantifier elimination in the theory of algebraically closed fields. Bibliography: 20 titles. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 316, 2004, pp. 5–29.     

Number of points on certain hyperelliptic curves defined over finite fields

For odd primes p and l such that the order of p modulo l is even, we determine explicitly the Jacobsthal sums _l(v), ψ_l(v), and ψ_2l(v), and the Jacobsthal–Whiteman sums and , over finite fields F_q such that . These results are obtained only in terms of q and l. We apply these results pertaining to the Jacobsthal sums, to determine, for each integer n1, the exact number of F_qⁿ-rational points on the projective hyperelliptic curves aY²Z^e−2=bX^e+cZ^e (abc≠0) (for e=l,2l), and aY²Z^l−1=X(bX^l+cZ^l) (abc≠0), defined over such finite fields F_q. As a consequence, we obtain the exact form of the ζ-functions for these three classes of curves defined over F_q, as rational functions in the variable t, for all distinct cases that arise for the coefficients a,b,c. Further, we determine the exact cases for the coefficients a,b,c, for each class of curves, for which the corresponding non-singular models are maximal (or minimal) over F_q.     

On the addition of residue classes modp

Given distinct residue classesa ₁ ,...,a _k modulo a primep, we consider the setS _j of all sums , whereli ₁<...<i _j k. We give a sufficient condition for the inequality |S _j |j(k–j)+1 to hold.