Modeling Experimental Nonlinear Dynamics and Chaotic Scenarios

(1)

RESEARCH NOTES

ON A DENSITY PROBLEM OF ERDÖS

SAFWAN AKBIK

(Received 13 April 1998 and in revised form 10 June 1998)

Abstract.For a positive integern, letP(n)denotes the largest prime divisor ofnand deﬁne the set:᏿(x)=᏿= {n≤x:ndoes not divideP(n)!}. Paul Erdös has proposed that

|S| =o(x)asx→ ∞, where|S|is the number ofn∈S. This was proved by Ilias Kastanas.

In this paper we will show the stronger result that|S| =O(xe^−1/4 logx).

Keywords and phrases. Number theory, primes, factorial, density, divisibility.

1991 Mathematics Subject Classiﬁcation. 11B05, 11N25.

Introduction. For a positive integern, letP(n)denote the largest prime divisor of nand deﬁne the set

᏿(x)=᏿=

n≤x:ndoes not divideP(n)!}. (1) Paul Erdös [1] proposed that|S| =o(x)asx→ ∞, where|S|is the number ofn∈S. A solution [3] was provided by Ilias Kastanas. There was also [3] a claim of proving that

|S(x)| =O(x/logx). In this paper, we show the stronger result.

Theorem. For some constanta >0, we have

|S| =O xe^−a√

logx

. (2)

In fact,a=1/4suﬃces.

Lemma1. Letν(n)be the number of distinct prime divisors ofn. Deﬁne S1=

n≤x:ν(n) >4kloglogx, k≥1

. (3)

Then

|S1| =O x

(logx)^k

(4) uniformly ink.

Proof. It is well known [2] that if d(m) is the number of divisors of m, then

m≤xd(m)=O(xlogx). Sinced(m)≥2^ν(m), O(xlogx)≥

m≤x

2^ν(m)≥

m∈S1

2^ν(m)≥

m∈S1

(logx)^(4log2)k≥ |S1|(logx)^k+1, (5)

and the lemma follows.

(2)

656 SAFWAN AKBIK

Lemma2. LetC(x)=C=(logx)^k, wherek=k(x)will be chosen later. Deﬁne S2=

n≤x:p²|nfor some primep > C

. (6)

Then

|S2| =O x

(logx)^k

. (7)

Proof. Sincen∈S2if and only ifn=tp²for someC < p≤√xand somet≤x/p²,

|S2| =

C<p≤√ x

x p²

≤

C<p≤√ x

x p²=O

x C

=O x

(logx)^k

. (8)

The ﬁrst big O in (8) follows since

p>C1/p² ≤ _∞

[C]du/u² = 1/[C] = O(1/C), forC≥1.

Lemma3. Let S3=

n≤x:p^α|nfor someα≥Tand some primeP≤C

, (9)

whereT=2logC. Then

|S3| =O x

(logx)^k

. (10)

Proof.

|S3| =

p≤Cα≥T

x p^α

≤2

p≤C

x

p^T ≤2 x 2^T _p

4

p²=Ox 2^T

=O x

C^2log2

≤O x

C

=O x

(logx)^k

.

(11)

The ﬁrst inequality in (11) is valid because

α≥T1/p^α≤1/p^T+1/p^T+1+ ··· ≤2/p^T and the second is valid becausep^T=2^T(p/2)^T≥2^T(p/2)²forT≥2.

Lemma4. LetS(x)=S−(S1∪S2∪S3), then, for any n∈S, we have

P(n)≤2CT . (12)

Proof. Letn∈S. Thenn∈Sand sondoes not divideP(n)!. There exists a prime p0dividingnsuch that

νp0(n) > νp0

P(n)!

, (13)

whereνp(m)denotes the largest integertsuch thatp^tdividesm. Sinceνp₀(P(n)!)≥ 1, (13) implies thatνp0(n)≥2. Sincen∈S2, it follows thatp0≤C. Alson∈S3, so thatT≥νp0(n). Hence,

T≥νp0(n) > νp0

P(n)!

≥P(n)

2p0 ≥P(n)

2C (14)

(3)

which implies (12). Note that the third inequality in (14) is true because νp(m!)≥ m/2pfor anymand anyp|m. This is because

νp(m!)≥ m

p

>m

p −1≥ m

2p, p=m, (15)

and[m/p]=1≥m/2pifp=m.

Proof of the Theorem. For n∈S, we haven∈S1∪S2∪S3. Thus, νp(n)≤ 4kloglogx. Also, ifp^αis any prime power dividingn, then one of the following two possibilities must occur:

(a) p≤Candα≤T, (b) p > Candα=0 or 1.

Case (a) generates at mostC(T+1)≤2CT prime powers. For Case (b), the number of prime powersp^αwithp > C andα≤1 is at mostP(n). By Lemma 4, this is at most 2CT. Hence, the number of possible prime powersp^αthat divide ann∈Sis at most 4CT. But such anncan be the product of at most 4kloglogxdistinct prime powers.

Therefore,

|S| ≤(4CT )^4k^loglogx=(8ClogC)^4k^loglogx

=e^4k^loglog^x(log8+kloglogx+logk+logloglogx)≤e^8k²^(loglogx)² (16) since log8+log(kloglogx)≤kloglogx, forkloglogx≥4.

Choosing

k=1 4·

logx

loglogx, (17)

(16) gives|S| ≤e^(1/2)logx=x^1/2. Hence, S=O

xe^−(1/4)√

logx

. (18)

From (17), we havex/(logx)^k=xe^−1/4√

logx. Lemmas 1, 2, and 3 imply that

|Si| =O xe^−1/4√

logx

, i=1,2,3. (19)

Finally,S=S∪[S∩(S1∪S2∪S3)]. Hence, (18) and (19) yield

|S| ≤ |S|+|S1|+|S2|+|S3| =O

xe^−(1/4)√

logx

, (20)

and (2) follows witha=1/4.

Remark. Ifπ(x)is the number of prime integers that are less than or equal tox, an early version of the prime numbers theorem asserts that

π(x)= _x

2

du logu+O

xe^−a√

logx

, (21)

for some constanta. Although the bigOterms in (19) and (2) are similar, there is no apparent relationship between the PNT and (2).

(4)

658 SAFWAN AKBIK References

[1] P. Erdös,A Proposed Problem, Amer. Math. Monthly98(1991), 965.

[2] G. H. Hardy and E. M. Wright,An Introduction to the Theory of Numbers, 5th ed., The Claren- don Press, Oxford University Press, New York, 1979. MR 81i:10002. Zbl 423.10001.

[3] I. Kastanas,The smallest factorial that is a multiple ofn, Amer. Math. Monthly101(1994), 179.

Akbik: Department of Mathematics, Hofstra University, Hempstead, NY11550, USA

(5)

Special Issue on

Modeling Experimental Nonlinear Dynamics and Chaotic Scenarios

Call for Papers

Thinking about nonlinearity in engineering areas, up to the 70s, was focused on intentionally built nonlinear parts in order to improve the operational characteristics of a device or system. Keying, saturation, hysteretic phenomena, and dead zones were added to existing devices increasing their behavior diversity and precision. In this context, an intrinsic nonlinearity was treated just as a linear approximation, around equilibrium points.

Inspired on the rediscovering of the richness of nonlinear and chaotic phenomena, engineers started using analytical tools from “Qualitative Theory of Diﬀerential Equations,”

allowing more precise analysis and synthesis, in order to produce new vital products and services. Bifurcation theory, dynamical systems and chaos started to be part of the mandatory set of tools for design engineers.

This proposed special edition of the Mathematical Prob- lems in Engineering aims to provide a picture of the impor- tance of the bifurcation theory, relating it with nonlinear and chaotic dynamics for natural and engineered systems.

Ideas of how this dynamics can be captured through precisely tailored real and numerical experiments and understanding by the combination of specific tools that associate dynamical system theory and geometric tools in a very clever, sophis- ticated, and at the same time simple and unique analytical environment are the subject of this issue, allowing new methods to design high-precision devices and equipment.

Authors should follow the Mathematical Problems in Engineering manuscript format described at http://www .hindawi.com/journals/mpe/. Prospective authors should submit an electronic copy of their complete manuscript through the journal Manuscript Tracking System athttp://

mts.hindawi.com/according to the following timetable:

Manuscript Due December 1, 2008 First Round of Reviews March 1, 2009 Publication Date June 1, 2009

Guest Editors

José Roberto Castilho Piqueira,Telecommunication and Control Engineering Department, Polytechnic School, The University of São Paulo, 05508-970 São Paulo, Brazil;

[email protected]

Elbert E. Neher Macau,Laboratório Associado de Matemática Aplicada e Computação (LAC), Instituto Nacional de Pesquisas Espaciais (INPE), São Josè dos Campos, 12227-010 São Paulo, Brazil ; [email protected] Celso Grebogi,Center for Applied Dynamics Research, King’s College, University of Aberdeen, Aberdeen AB24 3UE, UK; [email protected]

Hindawi Publishing Corporation http://www.hindawi.com