Geometric progressions in sumsets over finite fields

Given two sets A, B í \Bbb F_q^d{\cal A}, {\cal B}\subseteq {\Bbb F}_q^d , the set of d dimensional vectors over the finite field \Bbb F_q{\Bbb F}_q with q elements, we show that the sumset A+B = {a+b | a ? A, b ? B}{\cal A}+{\cal B} = \{{\bf a}+{\bf b}\ \vert\ {\bf a} \in {\cal A}, {\bf b} \in {\cal B}\} contains a geometric progression of length k of the form vΛ ^j , where j = 0,…, k − 1, with a nonzero vector v ? \Bbb F_q^d{\bf v} \in {\Bbb F}_q^d and a nonsingular d × d matrix Λ whenever # A # B 3 20 q^2d-2/k\# {\cal A} \# {\cal B} \ge 20 q^{2d-2/k} . We also consider some modifications of this problem including the question of the existence of elements of sumsets on algebraic varieties.     

Distribution of Nonlinear Congruential Pseudorandom Numbers Modulo Almost Squarefree Integers

The nonlinear congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. In this paper we present a new bound on the s-dimensional discrepancy of nonlinear congruential pseudorandom numbers over the residue ring modulo M for an “almost squarefree” integer M. It is useful to recall that almost all integers are of this type. Moreover, if the generator is associated with a permutation polynomial over we obtain a stronger bound “on average” over all initial values. This bound is new even in the case when M = p is prime.     

Arithmetic properties of the Ramanujan function

We study some arithmetic properties of the Ramanujan function τ(n), such as the largest prime divisorP (τ(n)) and the number of distinct prime divisors ω (τ (n)) of τ(n) for various sequences ofn. In particular, we show thatP(τ(n)) ≥ (logn)^33/31+o(1) for infinitely many n, and

Modular hyperbolas

We give a survey of a variety of recent results about the distribution and some geometric properties of points (x, y) on modular hyperbolas ${xy \equiv a\;(\mod m)}$ . We also outline a very diverse range of applications of such results, discuss multivariate generalisations and suggest a number of open problems of different levels of difficulty.     

Partitions into two Lehmer numbers

We prove an asymptotic formula for the number of representations of an integer as sum of two Lehmer numbers which implies that under some natural restrictions each sufficiently large integer is a sum of two such numbers.     

On the cycle structure of repeated exponentiation modulo a prime

In a recent work, Shallit and Vasiga have obtained several results about tails and cycles in orbits of repeated squaring. Some of these results have been based on the Extended Riemann Hypothesis. Here, we extend their result to repeated exponentiation with any fixed exponent e and also show that in fact classical unconditional results about the distribution of primes in arithmetic progressions, combined with very elementary arguments, are quite sufficient to generalise and give an unconditional proof of their asymptotic formulas.     

On products of primes and almost primes in arithmetic progressions

We show that for any integers a and m with m ≥ 1 and gcd(a,m) = 1, there is a solution to the congruence pr ≡ a (modm) where p is prime, r is a product of at most k = 17 prime factors and p, r ≤ m. This is a relaxed version of the still open question, studied by P. Erd?s, A. M. Odlyzko and A. Sárközy, that corresponds to k = 1 (that is, to products of two primes).     

On Some Properties of the Shrinking Generator

We obtain several results about the output rate and distribution ofzeros and ones of the shrinking generator associated with two linear recurringsequences. These results are based on various bounds on the number of zeros of linearrecurring sequences. Non-linear recurring sequences are considered aswell.     

On the Linear Complexity of the Naor–Reingold Pseudo-random Function from Elliptic Curves

We show that the elliptic curve analogue of the pseudo-random number function, introduced recently by M. Naor and O. Reingold, produces a sequence with large linear complexity. This result generalizes a similar result of F. Griffin and I. E. Shparlinski for the linear complexity of the original function of M. Naor and O. Reingold. The proof is based on some results about the distribution of subset-products in finite fields and some properties of division polynomials of elliptic curves.     

On the Multidimensional Distribution of Inversive Congruential Pseudorandom Numbers in Parts of the Period

 The inversive congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. In this paper we present the first nontrivial bounds on the multidimensional discrepancy of individual sequences of inversive congruential pseudorandom numbers in parts of the period. The proof is based on a new bound for certain incomplete exponential sums. (Received 3 December 1998)