Primes Represented by Binary Cubic Forms

Let f(x, y) be a binary cubic form with integral rational coefficients,and suppose that the polynomial f(x, y) is irreducible in Q[x,y] and no prime divides all the coefficients of f. We provethat the set f Z⁽²⁾ contains infinitely many primes unless f(a,b) is even for each (a,b) in Z², in which case the set contains infinitely many primes. 2000Mathematical Subject Classification: primary 11N32; secondary11N36, 11R44.     

Enumerating Transitive Finite Permutation Groups

Denote by f(n) the number of subgroups of the symmetric groupSym(n) of degree n, and by f_trans(n) the number of its transitivesubgroups. It was conjectured by Pyber [9] that almost all subgroupsof Sym(n) are not transitive, that is, f_trans(n)/f(n) tendsto 0 when n tends to infinity. It is still an open questionwhether or not this conjecture is true. The difficulty comesfrom the fact that, from many points of view, transitivity isnot a really strong restriction on permutation groups, and thereare too many transitive groups [9, Sections 3 and 4]. In thispaper we solve the problem in the particular case of permutationgroups of prime power degree, proving the following result.1991 Mathematics Subject Classification 20B05, 20D60.     

On locally repeated values of certain arithmetic functions,I

Let ν(n) denote the number of distinct prime factors of n. We show that the equation n + ν(n) = m + ν(m) has many solutions with n ≠ m. We also show that if ν is replaced by an arbitrary, integer-valued function f with certain properties assumed about its average order, then the equation n + f(n) = m + f(m) has infinitely many solutions with n ≠ m.     

Values of the Euler Function in Various Sequences

Let ϕ(n) and λ(n) denote the Euler and Carmichael functions, respectively. In this paper, we investigate the equation ϕ(n)^r = λ(n)^s, where r ≥ s ≥ 1 are fixed positive integers. We also study those positive integers n, not equal to a prime or twice a prime, such that ϕ(n) = p − 1 holds with some prime p, as well as those positive integers n such that the equation ϕ(n) = f(m) holds with some integer m, where f is a fixed polynomial with integer coefficients and degree degf > 1.     

A characterization of finite soluble groups

Let G be a finite soluble group of order m and let w(x₁, ...,x_n) be a group word. Then the probability that w(g₁, ..., g_n)= 1 (where (g₁, ..., g_n) is a random n-tuple in G) is at leastp^–(m–t), where p is the largest prime divisor ofm and t is the number of distinct primes dividing m. This contrastswith the case of a non-soluble group G, for which Abérthas shown that the corresponding probability can take arbitrarilysmall positive values as n .     

Sur L'equation Diophantienne (xn-1)/(x-1)=yq, III

In this paper we study the diophantine equation of the title,which was first introduced by Nagell and Ljunggren during thefirst half of the twentieth century. We describe a method whichallows us, on the one hand when n is fixed, to obtain an upperbound for q, and on the other hand when n and q are fixed, toobtain upper bounds for x and y which are far sharper than thosederived from the theory of linear forms in logarithms. We alsoshow how these bounds can be used even when they seem too largefor a straightforward enumeration of the remaining possiblevalues of x. By combining all these techniques, we are ableto solve the equation in many cases, including the case whenn has a prime divisor less than 13, or the case when n has aprime divisor which is less than or equal to 23 and distinctfrom q. 2000 Mathematical Subject Classification: primary 11D41;secondary 11J86, 11Y50.     

A uniform coprimality result for some arithmetic functions

Using analytic methods, an asymptotic formula, which holds uniformly for squarefree positive integers d in a suitable range, is obtained for the number of positive integers n ≤ x such that (d,f(n)) = 1, where f is an integer-valued multiplicative function such that f(p) is a polynomial in p for p prime, and where d has no prime divisor from a certain finite exceptional set. Examples of such functions f are Euler's function φ and the divisor functions σ_ν (ν = 1,2,…), which case d is assumed to be odd.     

Congruences De Sommes De Chiffres De Valeurs Polynomiales

Let m, g, q N with q 2 and (m, q – 1) = 1. For n N,denote by s_n(n) the sum of digits of n in the q-ary digitalexpansion. Given a polynomial f with integer coefficients, degreed 1, and such that f(N) N, it is shown that there exists C= C(f, m, q) > 0 such that for any g Z, and all large N, In the special case m = q = 2 and f(n)= n², the value C = 1/20 is admissible. 2000 Mathematics SubjectClassification 11B85 (primary), 11N37, 11N69 (secondary).     

Sommes D'Exponentielles et Entiers Sans Grand Facteur Premier

Let S(x,y) be the set S(x,y)= 1 n x : P(n) y, where P(n) denotesthe largest prime factor of n. We study , where f is a multiplicative function. When f=1and when f=µ, we widen the domain of uniform approximationusing the method of Fouvry and Tenenbaum and making explicitthe contribution of the Siegel zero. Soit S(x,y) l'ensemble S(x,y)= 1 n x : P(n) y, désigne le plus grand facteur premier den. Nous étudions , lorsque f est une fonction multiplicative. Quand f=1 et quand f=µ,nous élargissons le domaine d'approximation uniformeenutilisant la méthode développée par Fouvryet Tenenbaum et en explicitant la contribution du zérode Siegel. 1991 Mathematics Subject Classification: 11N25, 11N99.     

Complex Dynamics of Convergence Acceleration

Generalized Steffensen methods are nonderivative algorithmsfor the computation of fixed points of a function f. They replacethe functional iteration Z_m+1=f(Z_m) with Z_m+1=F_n(Z_m, where F_nis explicitly provided for every n 1 as a quotient of two Hankeldeterminants. In this paper we derive rules pertaining to thelocal behaviour of these methods. Specifically, and subjectto analyticity, given that is a bounded fixed point of f, thenit is also a fixed point of F_n. Moreover, unless f'() vanishesor is a root of unity, becomes a superattractive fixed pointof F_n of degree n; if f'() is a root of unity of minimal degreeq2, then is (as a fixed point of F_n) superattractive of degreemin {q-1, n}; if f'()=1, then is attractive for F_n; and, finally,if is superattractive of degree s (as a fixed point of f),then it becomes superattractive of degree (s + 1)^n–1(ns+ s + 1)–1. Attractivity rules change at infinity (providedthat f()=). Broadly speaking, infinity becomes less attractivefor F_n, Since one is interested in convergence to finite fixedpoints, this further enhances the appeal of generalized Steffensenmethods.     

Best Approximation in an Asymmetrically Weighted L1 Measure

Let f(x) be a given, real-valued, continuous function definedon an interval [a,b]of the real line. Given a set of m real-valued,continuous functions _j(x) defined on [a,b], a linear approximatingfunction can be formed with any real setA = {a₁, a₂,..., a_m}. We present results for determining A sothat F(A, x) is a best approximation to(x) when the measureof goodness of approximation is a weighted sum of |F(A, x)–f(x)|,the weights being positive constants, w, when F(A, x) f(x)and w2 otherwise (when w, = w2 = 1, the measure is the L₁, norm).The results are derived from a linear programming formulationof the problem. In particular, we give a theorem which shows when such bestapproximations interpolate the function at fixed ordinates whichare independent of f(x). We show how the fixed points can becalculated and we present numerical results to indicate thatthe theorem is quite robust.     

Triangle group representations and constructions of regular maps

A regular map of type {m,n} is a 2-cell embedding of a graphin an orientable surface, with the property that for any twodirected edges e and e' there exists an orientation-preservingautomorphism of the embedding that takes e onto e', and in whichthe face length and the vertex valence are m and n, respectively.Such maps are known to be in a one-to-one correspondence withtorsion-free normal subgroups of the triangle groups T(2,m,n).We first show that some of the known existence results aboutregular maps follow from residual finiteness of triangle groups.With the help of representations of triangle groups in speciallinear groups over algebraic extensions of Z we then constructivelydescribe homomorphisms from T(2,m,n)=y,z|y^m=zⁿ=(yz)²=1 intofinite groups of order at most c^r where c=c(m,n), such thatno non-identity word of length at most r in x,y is mapped ontothe identity. As an application, for any hyperbolic pair {m,n}and any r we construct a finite regular map of type {m,n} ofsize at most C^r, such that every non-contractible closed curveon the supporting surface of the map intersects the embeddedgraph in more than r points. We also show that this result isthe best possible up to determining C=C(m,n). For r>m thegraphs of the above regular maps are arc-transitive, of valencen, and of girth m; moreover, if each prime divisor of m is largerthan 2n then these graphs are non-Cayley. 2000 Mathematics SubjectClassification: 05C10, 05C25, 20F99, 20H25.     

On a Problem of Brocard

It is proved that, if P is a polynomial with integer coefficients,having degree 2, and 1 > > 0, then n(n – 1) ...(n – k + 1) = P(m) has only finitely many natural solutions(m,n,k), n k > n, provided that the abc conjecture is assumedto hold under Szpiro's formulation. 2000 Mathematics SubjectClassification 11D75, 11J25, 11N13.     

Arithmetic properties of Apery numbers

Let (A_n)_n1 be the sequence of Apéry numbers with a generalterm given by . In thispaper, we prove that both the inequalities (A_n) > c₀ loglog log n and P(A_n) > c₀ (log n log log n)^1/2 hold fora set of positive integers n of asymptotic density 1. Here,(m) is the number of distinct prime factors of m, P(m) is thelargest prime factor of m and c₀ > 0 is an absolute constant.The method applies to more general sequences satisfying botha linear recurrence of order 2 with polynomial coefficientsand certain Lucas-type congruences.     

The largest prime factor of X3+2

The largest prime factor of X³+2 was investigated in 1978 byHooley, who gave a conditional proo that it is infinitely oftenat least as large as X¹+, with a certain positive constant .It is trivial to obtain such a result with =0. One may thinkof Hooley's result as an approximation to the conjecture thatX³+2 is infinitely often prime. The condition required by Hooley,his R^* conjecture, gives a non-trivial bound for short Ramanujan–Kloostermansums. The present paper gives an unconditional proof that thelargest prime factor of X³+2 is infinitely often at least aslarge as X¹⁺, though with a much smaller constant than thatobtained by Hooley. In order to do this we prove a non-trivialbound for short Ramanujan–Kloosterman sums with smoothmodulus. It is also necessary to modify the Chebychev method,as used by Hooley, so as to ensure that the sums that occurdo indeed have a sufficiently smooth modulus. 2000 MathematicsSubject Classification: 11N32.     

A Generalised Skolem-Mahler-lech Theorem for Affine Varieties

The Skolem–Mahler–Lech theorem states that if f(n)is a sequence given by a linear recurrence over a field of characteristic0, then the set of m such that f(m) is equal to 0 is the unionof a finite number of arithmetic progressions in m 0 and afinite set. We prove that if X is a subvariety of an affinevariety Y over a field of characteristic 0 and q is a pointin Y, and is an automorphism of Y, then the set of m such that^m(q) lies in X is a union of a finite number of complete doubly-infinitearithmetic progressions and a finite set. We show that thisis a generalisation of the Skolem–Mahler–Lech theorem.     

On the number of non-isomorphic matroids

Let f(n) denote the number of non-isomorphic matroids on an n-element set. In 1969, Welsh conjectured that, for all non-negative integers m and n, f(m+n)f(m)f(n). In this paper, we prove this conjecture.     

Parity of the partition function

Although much is known about the partition function, little is known about its parity. For the polynomials D(x):=(Dx²+1)/24, where , we show that there are infinitely many m (resp. n) for which p(D(m)) is even (resp. p(D(n)) is odd) if there is at least one such m (resp. n). We bound the first m and n (if any) in terms of the class number h(−D). For prime D we show that there are indeed infinitely many even values. To this end we construct new modular generating functions using generalized Borcherds products, and we employ Galois representations and locally nilpotent Hecke algebras.     

The density of prime divisors in the arithmetic dynamics of quadratic polynomials

Let f [x], and consider the recurrence given by a_n = f(a_{n –1}), with a₀ . Denote by P(f, a₀) the set of prime divisorsof this recurrence, that is, the set of primes dividing at leastone non-zero term, and denote the natural density of this setby D(P(f, a₀)). The problem of determining D(P(f, a₀)) whenf is linear has attracted significant study, although it remainsunresolved in full generality. In this paper, we consider thecase of f quadratic, where previously D(P(f, a₀)) was knownonly in a few cases. We show that D(P(f, a₀)) = 0 regardlessof a₀ for four infinite families of f, including f = x² + k,k \{–1}. The proof relies on tools from group theoryand probability theory to formulate a sufficient condition forD(P(f, a₀)) = 0 in terms of arithmetic properties of the forwardorbit of the critical point of f. This provides an analogy toresults in real and complex dynamics, where analytic propertiesof the forward orbit of the critical point have been shown todetermine many global dynamical properties of a quadratic polynomial.The article also includes apparently new work on the irreducibilityof iterates of quadratic polynomials.