See discussions, stats, and author profiles for this publication at: [Link]

net/publication/269806702

Applications of Number Theory in Statistics

Article  in  Bonfring International Journal of Data Mining · September 2012

DOI: 10.9756/BIJDM.1340

CITATIONS READS
2 5,599

1 author:

A.M.s Ramasamy
Vel Tech Rangarajan Dr Sagunthala R&D Institute of Science & Technology
46 PUBLICATIONS   164 CITATIONS   

SEE PROFILE

All content following this page was uploaded by A.M.s Ramasamy on 12 February 2015.

The user has requested enhancement of the downloaded file.

Bonfring International Journal of Data Mining, Vol. 2, No. 3, September 2012 7

Applications of Number Theory in Statistics

A.M.S. Ramasamy

Abstract--- There have been several fascinating x 11 12 13 14 15 16 17 18 19 20

applications of Number Theory in Statistics. The purpose of 5 5 6 6 6 6 7 7 8 8
this survey paper is to highlight certain important such
applications. Prime numbers constitute an interesting and Let denote the nth prime. With this notation, we have
challenging area of research in number theory. Diophantine
equations form the central part of number theory. An equation (1)
requiring integral solutions is called a Diophantine equation.
In the first part of this paper, some problems related to prime The following are well known results on primes:
numbers and the role of Diophantine equations in Design Prime number theorem: The number of prime’s not
Theory is discussed. The contribution of Fibonacci and Lucas exceeding x is asymptotic to .
numbers to a quasi-residual Metis design is explained. A
famous problem related to finite fields is the Discrete Tchebychef’s theorem: The order of magnitude of
Logarithm problem. In the second part of this paper, the is .
structure of Discrete Logarithm is discussed. An interesting question is to find how the prime pair’s p,
Keywords--- Distribution of Primes, Diophantine p+2 are distributed.
Equations, Design, Fibonacci and Lucas Numbers, Discrete
logarithm Problem III. THE POLYNOMIAL OF EULER
There have been several attempts by researchers to find out
polynomials which would yield prime numbers only.
I. INTRODUCTION Leonhard Euler (1707-1783) considered the

N UMBER theory is perhaps the oldest branch of

Mathematics and consequently there are several research
areas within the realm of number theory. Techniques from
polynomial where x is presumed to take
integral values only. Surprisingly, this polynomial takes
integral values only for several consecutive integral values of
other branches of knowledge may prove handy in solving x, starting from 0, as shown in the following tables:
some of the problems in number theory and vice versa. The x 0 1 2 3 4 5 6 7 8 9 10
aim of this paper is to stress the importance of inter- 4 4 4 5 6 7 8 9 11 13 15
disciplinary approach in research, especially the linkages f(x)
1 3 7 3 1 1 3 7 3 1 1
between number theory and Statistics. Certain specific
problems are discussed to illustrate the applications of number 1
x 12 13 14 15 16 17 18 19 20
theory in Statistics and to bring out the scope of inter- 1
dependence of the two subjects. 1
19 22 25 28 31 34 38 42 46
f(x) 7
7 3 1 1 3 7 3 1 1
II. PRIME NUMBERS 3

For detailed account of prime numbers, one may refer 2

[Link] [7]. The most perplexing behaviour of integers is x 22 23 24 25 26 27 28 29 30
1
that of prime numbers. In spite of the best efforts put in by 5
different researchers, understanding the several properties of 54 59 64 69 74 79 85 91 97
f(x) 0
7 3 1 1 3 7 3 1 1
prime numbers continues to pose insurmountable difficulties. 3
This is due to the variations in the properties possessed by
prime numbers. The distribution of primes is a fascinating area x 31 32 33 34 35 36 37 38 39
of research.
10 109 116 123 130 137 144 152 164
Let denotes the number of prime’s not exceeding x. f(x)
33 7 3 1 1 3 7 3 1
We have the following table of values:
x 1 2 3 4 5 6 7 8 9 10
However, when x = 40, we have f(x) = +40+41=
0 1 2 2 3 3 4 4 4 4
40(40+1)+41 = , associating a composite value for f(x).
Euler’s polynomial is an example to show that there cannot be
A.M.S. Ramasamy, Department of Mathematics, Ramanujan School of a polynomial taking prime values only.
Mathematical Sciences, Pondicherry University, Puducherry, India. E-mail:
amsramasamy@[Link]

DOI: 10.9756/BIJDM.1340

ISSN 2277 - 5048 | © 2012 Bonfring

Bonfring International Journal of Data Mining, Vol. 2, No. 3, September 2012 8

Similar to Euler’s polynomial, the following polynomials X 600 700 800 900 1000
also assume prime values only for the consecutive values of x A(x) 1174 1357 1569 1759 1941
provided within parentheses. 1.957 1.939 1.961 1.954 1.941
+11 (x=0, 1,...,10), +29 (x=0, 1,...,28), +x+17 (x=0,
He conjectured that has a finite limit of 1.9435964...
1,...,15), +39x+37 (x=0, 1,...,17), +4x+59 (x=0,
1,...,13), + +17 (x=0, 1,...,10) +29 +101 (x=0, as . In [1], he has presented several techniques to obtain
1,...,19). the estimates for the error term in .

When x is a natural number, it has been proved that no

V. DIOPHANTINE EQUATIONS
polynomial f(x) with integral coefficients, not a constant, can
be prime for all x, or for sufficiently large x (see for e.g. G.H. An equation requiring integral solutions is called a
Hardy and E.M. Right [3]). Diophantine equation. Diophantus of Alexandria was
interested in the integral solutions of algebraic equations and
We observe that it would be an interesting problem to find hence the nomenclature of Diophantine equations. These
out probabilistic estimates of consecutive prime (or equations form the central part of number theory. A standard
composite) values assumed by Euler’s polynomial for x > 39 reference for Diophantine equations is L.J. Mordell [5].
or the other polynomials specified above for x exceeding the
specified integral value. A. Square-Free Natural Number
A. Some Unsolved Problems Pertaining To Primes A natural number n is said to be square-free if it is not
divisible by the square of a number > 1. Therefore n is square-
Are there infinitely many primes given by the free if and only if it is the product of distinct primes.
polynomial ?
Is there always a prime between and ? An interesting problem is to determine the probability that
It is worthwhile to try the above problems with a given natural number n is square-free. Gauss observed that
probabilistic approach. the probability that two integers should be relatively prime
is . The probability that a number should be square-free is
IV. A PROBLEM RELATED TO EULER’S ARITHMETIC (see for e.g. G.H. Hardy and E.M. Right [3] ).
FUNCTION
B. Pell’s Equation
Let n be a given natural number> 1. Euler’s ∅-function
Let D be a given square-free natural number. The equation
associates with n the number of positive integers less than and
prime to n. By convention, is taken as 1. We have the (4)
following table of values:
is known as Pell’s equation. For a given square-free natural
n 1 2 3 4 5 6 7 8 9 10
number d, this equation always has integer solutions in x and y
∅(n) 1 1 2 2 4 2 6 4 6 4
and the number of solutions is infinite. Other general forms of
Pell’s equation are
n 11 12 13 14 15 16 17 18 19 20
∅(n) 10 4 12 6 8 8 16 6 18 8 and (5)

(6)
Consider the prime factorization of n. If ...
where p, q ... are distinct primes, then where N is a non-zero integer. These general forms may not
possess integral solutions for a given N or a square-free D. It
(2)
is of interest to note that Pell’s equation for a special value of
D is related to a Design as brought out in the sequel.
P.T. Bateman [1] considered the distribution of values of
Euler’s ∅-function. He took as the number of positive VI. DESIGN THEORY
integers n with and defined the function
An important branch of Statistics is Design Theory. A
. (3) design can be thought of as a point in The parameters
associated with a design form a quintuple (v, b, r, k, as
i.e., is the number of positive integer’s n descrfibed below:
with . He considered the function . The following
Let V denote a finite set consisting of v elements. By a
values were obtained by him: block we mean a subset of V. We consider b blocks. It is
X 100 200 300 400 500 assumed that each element of V is in r blocks where r b. We
A(x) 198 395 588 790 971 refer to r as the replication number of the design. Let k denote
the number of varieties in each block. It is assumed that every
1.980 1.975 1.960 1.975 1.942
pair elements of V appears together in blocks where b.
The number is called the co-valency for the design. The
following relations hold for the parameters of the design:

ISSN 2277 - 5048 | © 2012 Bonfring

Bonfring International Journal of Data Mining, Vol. 2, No. 3, September 2012 9

(7) (17)

(8) The first few Fibonacci and Lucas numbers are furnished
in the following table:
The contribution of number theory to designs will be
s 0 1 2 3 4 5 6 7 8
considered in the sequel. Towards this purpose, we consider a
special type of a design.
0 1 1 2 3 5 8 13 21
A. Metis Design
By a Metis design we mean a block design with parameter 2 1 3 4 7 11 18 29 47
set (v, b, r, k, satisfying the additional relation
(9)
s 9 10 11 12 13 14 15
B. Quasi-Residual Metis Design
34 55 89 144 233 377 610
A quasi-residual Metis design has the additional property
(10) 76 123 199 322 521 843 1364

Consider equations (7) through (10). From (10) we

have . Using this in (8), we get . One can observe that the successive pairs of Fibonacci and
Substituting for v from (9), we obtain the relation Lucas numbers have the following property:
(11)

Treating (11) as a quadratic equation in k, we are led to the

These specific results prompt us to try an induction
relation
approach to have a general result. By induction we see that

Thus the corresponding even subscripted terms in the

Since k cannot take negative values, we get Lucas and Fibonacci sequences satisfy the Pell’s equation (15)
and consequently they lead to a quasi-residual Metis design. In
(12)
view of this result, the parameters of a quasi-residual Metis
design are obtained in terms of the Lucas and Fibonacci
In order that k assumes integral values, a necessary numbers as:
condition is that is the square of a natural number.
Let g denote the greatest common divisor of 5r+4 and r. Then
g 4. This implies that is a square. Hence each one of
and shall be perfect squares. Considering modulo 4, it is VII. THE PROBLEM OF DISCRETE LOGARITHM
seen that g cannot take the value of 2. Hence g = 1 or 4. In Let p be an odd prime. The discrete logarithm problem is
either case 5r+4 and r are both squares. Therefore there exist to find x = (y) in the finite field i.e., to find the value(s)
natural numbers x and y such that x in such that y (mod p). No algorithm is currently
and (13) available for this problem. There are applications of this
problem in cryptography which is the subject of sending
(14) messages in a secret way, ensuring the security of the
information (see for e.g., [Link] [6]). The problem of
Thus we see that x and y are related by the following mapping the discrete logarithm has been considered by
equation [Link] and [Link] [2]. The structure in the discrete
logarithm has been studied by [Link] [4].
(15)
The discrete logarithm can be viewed as a function. The
Equation (15) is the Pell’s equation – with problem is to determine the inverse of x (mod p). A
D = 5 and N = [Link] a quasi-residual Metis design is related functional graph may be used a tool for this problem. The
to the Pell’s equation. values of x can be represented by nodes of a graph and arrows
may be drawn for each one of the mappings. A functional
C. Relationship with Fibonacci and Lucas Numbers graph is a directed graph such that each vertex must have
Fibonacci numbers { } and Lucas numbers { } are exactly one edge directed out from it. An m-ary functional
recursively defined as follows (see for e.g. [Link] and graph is a functional graph where each node has in-degree of
[Link] [3]). exactly zero or m.
(16)

ISSN 2277 - 5048 | © 2012 Bonfring

Bonfring International Journal of Data Mining, Vol. 2, No. 3, September 2012 10

Let us consider a few specific cases to illustrate the Let r be an element of . Let e be the smallest natural
procedure involved. For the functional graph of 2 (mod 5), number such that = 1 (mod p). We say that r is a primitive
consider the successive integral powers of 2 and reduce them root modulo p if . Let r be any primitive root modulo
modulo 5. We have p and g D. Cloutier
2 (mod 5), 4 (mod 5), 3 (mod 5), 1 (mod and J. Holden [2] that the values of g that produce an m-ary
5).Taking into account the exponent and the result after graph are precisely those for which gcd (α, p-1) = m.
reducing modulo 5, we obtain the forward correspondence In the problem of discrete logarithm, A. Hoffman [4] has
taken b as a primitive root modulo p and considered three
parameters associated with a functional graph, viz. the number
of cycles, the maximum cycle length and the weighted average
From this correspondence, we separate the cycles and get cycle length. He has shown that the structure of discrete
. Each cycle is represented by logarithm can be analysed by statistical investigation of these
means of a directed graph. The functional graph for this case three parameters. He has illustrated how comparisons are
and a few other examples are shown below. possible between random permutations and those constructed
from the solution to the discrete logarithm problem by
considering the expected values of the three parameters in
both cases.
1 4 3
2
3
22 2 With the distribution of cycle lengths following Poisson
2 22 2 distribution, has shown how ANOVA tests can be carried out
22
22 4 2 for mean number of cycle components, number of components
21
2 2 variance, mean maximum cycle length, maximum cycle
2 2 variance, mean average cycle length and average cycle
Functional graph 2for 2 (mod 5) Functional graph for variance. Selecting 30 primes in the range 99991 – 106921
2
4(mod 5) and employing t-test and Anderson-Darling test, he has
1 4 9 derived the statistical results for the three parameters of the
1 7
0
functional graphs concerning the primes to illustrate the
2 2 8 structure in the discrete logarithm.
2
2
1 6
2 1 5 3
VIII. CONCLUSION
2 1
2 In the foregoing discussion, some of the linkages between
Functional graph for 7 (mod 13)
2 Number Theory and Statistics have been furnished. There is
2
much scope for probing into the applications of Number
2
1 3 1 2 9 4 1
Theory in Statistics and vice versa. Distribution of prime
2
2
2
2
0
1
2
2
2
2
2
2
3
2
numbers is a challenging area of research. When the
2
1 2
2
8
2
2 1
4
2 2 1
2
2 parameters in a design become large, analysis of the design
6 2 2
2 2
2
2 2 becomes quite complex and so one requires more
2 2
2
2
5 2 6
2
2
1
5
7
2
2
1
1
computational skill. Understanding of the properties of primes
2
2
2 2 2 2 and solving a discrete logarithm problem by means of
2 2 2 2
2
2 2 functional graphs require high-end computing power. With the
presently available computational capabilities due to
Functional graph for 3 (mod 17) technological development, the future research work holds
promise and one may expect tangible results in this interesting
1
8
1
2
5
2
1
0
1
2
field of research.
8 2 5
2 2
2 9 2 2 6
2
1 3
2 2
2
2
2
2
2 2
2
2
2
2
1
2
2
2
IX. ACKNOWLEDGEMENT
1
2 1
2 7
2 2
1 2
4
2
6
6
2 5
2
2
The author is thankful to the referee for the suggestions
2
2 2
2
2 2 towards the improvement of the paper.
2 2
2
8 4 1 1
2
2
2
2
7
2
3
2
REFERENCES
2 2
2 2
2 2 [1] P.T. Bateman, “The distribution of values of Euler’s ∅-function”, Acta
Arith., Volume 21, Pp. 329 – 345, 1972
Functional graph for 5 (mod 19) [2] D. Cloutier and J. Holden, “Mapping the discrete logarithm”, Involve,
In the functional graph for 4 (mod 5), the nodes 2 and 3 are Volume 3, Issue 2, Pp. 197 – 213, 2010
[3] G.H. Hardy and E.M. Wright, “An introduction to the theory of
not parts of any cycles. It is of interest to consider a functional numbers”, Oxford University Press, London, 1975.
graph wherein each node is part of a cycle. In this regard, we [4] A. Hoffman, “Statistical investigation of structure in the discrete
need the following: logarithm”, Rose-Hulman Undergraduate Mathematics Journal,
Volume10, Issue 2, Pp. 1 – 20, 2009
[5] L.J. Mordell, “Diophantine equations”, Academic Press, London, 1969

ISSN 2277 - 5048 | © 2012 Bonfring

Bonfring International Journal of Data Mining, Vol. 2, No. 3, September 2012 11

[6] A.M. Odlyzko, “Discrete logarithms in finite fields and their

cryptographic significance” in “Advances in Cryptology: Proceedings of
EUROCRYPT 84”, Lecture Notes in Computer Science, Springer-
Verlag, Volume 209, Pp. 242 – 314, 1985
[7] P. Ribenboim, “The new book of prime number records”, Springer
Verlag, New York, 1996.

Dr.A.M.S. Ramasamy obtained [Link]., degree in

Mathematics from University of Madras in 1971 and
Ph.D degree in Mathematics from Indian Institute of
Technology, Kanpur in 1983. He has served on the
faculties of Loyola College, Chennai and A.V.C.
College (Autonomous), Mayiladuthurai. Presently he
is serving as Dean of Ramanujan School of
Mathematical Sciences at Pondicherry University,
Pondicherry. A specialist in Diophantine equations, he has had a method
named after him for a system of Pell’s quations. His research interests include
Number Theory, Mathematical Modelling, Fuzzy Set Theory and Systems
Analysis. He has guided four candidates in doctoral work.

ISSN 2277 - 5048 | © 2012 Bonfring

View publication stats