Patterns of quadratic residues and nonresidues for infinitely many primes

If S is a nonempty, finite subset of the positive integers, we address the question of when the elements of S consist of various mixtures of quadratic residues and nonresidues for infinitely many primes. We are concerned in particular with the problem of characterizing those subsets of integers that consist entirely of either (1) quadratic residues or (2) quadratic nonresidues for such a set of primes. We solve problem (1) and we show that problem (2) is equivalent to a purely combinatorial problem concerning families of subsets of a finite set. For sets S of (essentially) small cardinality, we solve problem (2). Related results and some associated enumerative combinatorics are also discussed.     

The distribution of quadratic residues and nonresidues in arithmetic progressions

We prove some results concerning the distribution of quadratic residues and nonresidues in arithmetic progressions in the setting \( {{\mathbb{F}}_p}={{\mathbb{Z}} \left/ {{p\mathbb{Z}}} \right.} \) , where p is a large prime.     

Consecutive residues and nonresidues of polynomials

The author examines the distribution of common residues (mod p) of any polynomialsf ₁(x) andf ₂(x) and the distribution of consecutive residues and nonresidues of any degree.Translated from Matematicheskie Zametki, Vol. 7, No. 1, pp. 97–107, January, 1970.     

An estimate for the number of consecutive quadratic residues

The problem of estimation of the maximal number H of consecutive integer numbers such that they all are either quadratic residues or quadratic nonresidues modulo a prime number p is considered.     

On sums and products of quadratic residues

The paper deals with some special topics in connection with sums and products of quadratic residues. Some attention is devoted to primitive roots as a useful tool for these problems. Numerical results obtained by aid of a computer will also be presented.     

On consecutive quadratic non-residues: a conjecture of Issai Schur

Issai Schur once asked if it was possible to determine a bound, preferably using elementary methods, such that for all prime numbers p greater than the bound, the greatest number of consecutive quadratic non-residues modulo p is always less than p^1/2. This paper uses elementary methods to prove that 13 is the only prime number for which the greatest number of consecutive quadratic non-residues modulo p exceeds p^1/2.     

On the first occurrence of certain patterns of quadratic residues and non-residues

Effective upper bounds are obtained for the first occurrence of certain mixed patterns of quadratic residues and non-residues using the character sum estimates of D. A. Burgess and a proof of a conjecture of E. Lehmer.     

Cubic residues and binary quadratic forms

Let p>3 be a prime, u,v,d∈Z, gcd(u,v)=1, p?u²−dv² and , where is the Legendre symbol. In the paper we mainly determine the value of by expressing p in terms of appropriate binary quadratic forms. As applications, for we obtain a general criterion for and a criterion for εd to be a cubic residue of p, where εd is the fundamental unit of the quadratic field . We also give a general criterion for , where {Un} is the Lucas sequence defined by U₀=0, U₁=1 and Un+1=PUn−QUn−1 (n?1). Furthermore, we establish a general result to illustrate the connections between cubic congruences and binary quadratic forms.     

Quartic residues and binary quadratic forms

Let be a prime, m∈Z and . In this paper we obtain a general criterion for m to be a quartic residue in terms of appropriate binary quadratic forms. Let d>1 be a squarefree integer such that , where is the Legendre symbol, and let ε_d be the fundamental unit of the quadratic field . Since 1942 many mathematicians tried to characterize those primes p so that ε_d is a quadratic or quartic residue . In this paper we will completely solve these open problems by determining the value of , where p is an odd prime, and . As an application we also obtain a general criterion for , where {u_n(a,b)} is the Lucas sequence defined by and .     

Simple arguments on consecutive power residues

By some extremely simple arguments, we point out the following:

(i)

If n is the least positive kth power non-residue modulo a positive integer m, then the greatest number of consecutive kth power residues mod m is smaller than m/n.

(ii)

Let OK be the ring of algebraic integers in a quadratic field with d∈{−1,−2,−3,−7,−11}. Then, for any irreducible π∈OK and positive integer k not relatively prime to , there exists a kth power non-residue ω∈OK modulo π such that .

     

Abelian groups and quadratic residues in weak arithmetic

We investigate the provability of some properties of abelian groups and quadratic residues in variants of bounded arithmetic. Specifically, we show that the structure theorem for finite abelian groups is provable in S₂² + iWPHP(Σ₁^b), and use it to derive Fermat's little theorem and Euler's criterion for the Legendre symbol in S₂² + iWPHP(PV) extended by the pigeonhole principle PHP(PV). We prove the quadratic reciprocity theorem (including the supplementary laws) in the arithmetic theories T₂⁰ + Count₂(PV) and I Δ₀ + Count₂(Δ₀) with modulo‐2 counting principles (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Constructions of optimal variable-weight OOCs via quadratic residues

Variable-weight optical orthogonal code (OOC) was introduced by G. C. Yang [IEEE Trans. Commun., 1996, 44: 47–55] for multimedia optical CDMA systems with multiple quality of service (QoS) requirements. In this paper, seven new infinite classes of optimal (v, {3, 4, 6}, 1,Q)-OOCs are constructed.     

On the quadratic character of quadratic units

Let be a prime. Let a,b∈Z with p?a(a²+b²). In the paper we mainly determine by assuming p=c²+d² or p=Ax²+2Bxy+Cy² with AC−B²=a²+b². As an application we obtain simple criteria for εD to be a quadratic residue , where D>1 is a squarefree integer such that D is a quadratic residue of p, εD is the fundamental unit of the quadratic field with negative norm. We also establish the congruences for and obtain a general criterion for p|U(p−1)/4, where {Un} is the Lucas sequence defined by U₀=0, U₁=1 and Un+1=bUn+k²Un−1(n?1).     

On long runs of heads and tails II

In a string ofn independent coin tosses we consider the difference between the lengths of the longest blocks of consecutive heads resp. tails. A complete characterization of the a.s. limit properties of this quantity is proved.     

Successes,runs and longest runs

The probability distribution of the numbeer of success runs of length k ( >/ 1) in n ( ⩾ 1) Bernoulli trials is obtained. It is noted that this distribution is a binomial distribution of order k, and several open problems pertaining to it are stated. Let S_n and L_n, respectively, denote the number of successes and the length of the longest success run in the n Bernoulli trials. A formula is derived for the probability P(L_n ⩽ k | S_n = r) (0 ⩽ k ⩽ r ⩽ n), which is alternative to those given by Burr and Cane (1961) and Gibbons (1971). Finally, the probability distribution of X_{n, Ln}^(k) is established, where X_{n, Ln}^(k) denotes the number of times in the n Bernoulli trials that the length of the longest success run is equal to k.     

Diophantine equations with products of consecutive values of a quadratic polynomial

Let a, b, c, d be given nonnegative integers with a,d?1. Using Chebyshev?s inequalities for the function π(x) and some results concerning arithmetic progressions of prime numbers, we study the Diophantine equation