Analytical Representations of Divisors of Integers
Krzysztof Maślanka




Analytical Representations
of Divisors of Integers
    Krzysztof Maślanka
e-mail: krzysiek2357@gmail.com


Institute for the History of Science
Polish Academy of Sciences
    
=======================================================================================================================




Certain analytical expressions which "feel" the divisors of natural numbers
are investigated. We show that these expressions encode to some extent the
well-known algorithm of the sieve of Eratosthenes.

Most part of the text is written in pedagogical style, however some formulas
are new.

MSC: Primary 11A51; Secondary 26A06





§ NOTATION AND CONVENTIONS


Throughout this paper we shall adopt the following notation and conventions:
n is a given natural number and k is a possible divisor of n. If k
actually divides n then j=n/k. Let f(x) denotes any real analytic
function defined in the neighborhood of the origin by a power series

    f(x)=∑_j=0^∞c_jx^j

with all c_j≠0 (i=1,2,3...). It will be shown that j is also the
exponent of x in the expansion (<ref>) around zero and j labels
half-lines or rays of divisors (see below).



§ MOTIVATION


The theory of divisors of integers is the cornerstone of elementary number
theory. It is convenient to introduce the characteristic function for
divisors:

Definition. For any n,k∈


ℕ

    _α_nk:={
    
    0pt1  if   k| n0  if   k∤
    n
    
    .



Another pretty obvious (and rather useless in numerical calculations)
representation of (<ref>) is:

    _α_nk=1/Γ(  1-mod(
    n,k)  )

where Γ(s) denotes the Euler gamma function and mod
(  n,k) gives the remainder on division of n by k. In fact
(<ref>) is more general than (<ref>) since it may be calculated
also for non-integer or even complex values of n and k but this leads to
some interpretation difficulties which we shall not discuss here.

Consider the following expression for some natural numbers n and k:

    α_nk=.  d^n/dx^ne^x^k|
    _x=0

We will prove the following

Theorem. Apart from a trivial normalization factor,
_α_nk defined in formula (<ref>) is equal to
α_nk defined in (<ref>).

Proof. Expanding the exponential function in (<ref>) in power
series and performing term-by-term differentiation we get:

    α_nk=.  d^n/dx^n
    
    
    ∑_j=0^∞
    (  x^k)  ^j/j!| _x=0=.
    
    
    ∑_j=0^∞
    1/j!d^n/dx^nx^jk|
    _x=0

Recall the general formulas for the n-th derivative of x^p with respect
to x

    d^n/dx^nx^p=Γ(  p+1)
    /Γ(  p+1-n)  x^p-n=n!pnx^p-n


    d^n/dx^nx^p=(  -1)  ^n
    Γ(  n-p)  /Γ(  -p)  x^p-n

where the second formula stems from properties of the gamma function and is
suitable for integer negative p (see e.g. <cit.>). Note that the
order of derivative n does not have to be integer but for integer n both
(<ref>) and (<ref>) reduce to the
well-known elementary differentiation rule. Using (<ref>)
we get:

    α_nk=.
    
    
    ∑_j=0^∞
    1/j!Γ(  jk+1)  /Γ(  jk+1-n)
    x^jk-n| _x=0.  =n!
    
    
    ∑_j=0^∞
    1/j!jknx^jk-n| _x=0

By simple inspection of (<ref>) we see why this expression "feels" the
divisors of the integer n. Indeed, when taking the limit x→0 the
only non-zero term in the series appears when jk=n for some integer j, and
this occurs if and only if k divides n. All terms with jk>n disappear in
the limit x→0 whereas those with jk<n, although singular in
x=0, vanish since the binomial coefficient term is zero. Therefore, in the
summation (<ref>) at most only one term can survive in the limit
process.▪

The above reasoning might appear far too excessive. However, it guarantees
that among divisors none have been omitted. It should also be stressed that it
may be used as a starting point for various generalizations since n need not
to be integer.

It is easy to guess the normalizing factor:

    α_nk=1/n!(  n/k)  !.  d^n/dx^ne^x^k| _x=0

Using the same reasoning we can derive similar expression for α_nk:

    α_nk=(  k!)  ^n/k/n!(  n/k)
    !.  d^n/dx^ne^x^k/k!|
    _x=0





§ SIMPLE EXAMPLE


In a natural way coefficients α_nk may be regarded as a square
matrix of arbitrarily large dimension where the running integer n labels
rows and the potential divisor k labels columns. The entries of this matrix
are either one or zero depending on whether k divides n or not. This
matrix is always triangular, since of course no divisor can exceed a given
number, and its determinant (for any dimension) is 1.

    [ n k   1   2   3   4   5   6   7   8   9  10 ...;   1   1   0   0   0   0   0   0   0   0   0 ...;   2   1   1   0   0   0   0   0   0   0   0 ...;   3   1   0   1   0   0   0   0   0   0   0 ...;   4   1   1   0   1   0   0   0   0   0   0 ...;   5   1   0   0   0   1   0   0   0   0   0 ...;   6   1   1   1   0   0   1   0   0   0   0 ...;   7   1   0   0   0   0   0   1   0   0   0 ...;   8   1   1   0   1   0   0   0   1   0   0 ...;   9   1   0   1   0   0   0   0   0   1   0 ...;  10   1   1   0   0   1   0   0   0   0   1 ...; ... ... ... ... ... ... ... ... ... ... ...     ]

(Matrix (<ref>) is closely related to the Redheffer matrix, see
e.g. <cit.>, <cit.>.) Introducing

    σ_0(n):=
    
    
    ∑_k=1^n
    α_nk

we see that σ_0(n) just counts the number of all divisors of a given
n including both unity and n itself.

It is known (see e.g. <cit.>) that the inverse of matrix
(<ref>) is:

    β_nk={
    
    
    0ptμ(  n/k)    if   k|
    n0  if   k∤ n
    
    .

where μ denotes the Möbius function:

    μ(n)={c]l
    0 if n has squared prime factor
    +1 if n is a square-free positive integer with an even number of prime
    factors
    -1 if n is a square-free positive integer with an odd number of prime
    factors
    .


    [ n k   1   2   3   4   5   6   7   8   9  10 ...;   1   1   0   0   0   0   0   0   0   0   0 ...;   2  -1   1   0   0   0   0   0   0   0   0 ...;   3  -1   0   1   0   0   0   0   0   0   0 ...;   4   0  -1   0   1   0   0   0   0   0   0 ...;   5  -1   0   0   0   1   0   0   0   0   0 ...;   6   1  -1  -1   0   0   1   0   0   0   0 ...;   7  -1   0   0   0   0   0   1   0   0   0 ...;   8   0   0   0  -1   0   0   0   1   0   0 ...;   9   0   0  -1   0   0   0   0   0   1   0 ...;  10   1  -1   0   0  -1   0   0   0   0   1 ...; ... ... ... ... ... ... ... ... ... ... ...     ]

Note that the numbers in (<ref>) when summed in rows give zero
except for the first row which stems from the following identity:

    ∑_d|nμ(d)=δ_n,1

Matrices (<ref>) and (<ref>) are visualized in
Figure 1.

Somewhat similar but purely qualitative results have been published in
<cit.>.















    < g r a p h i c s >



Figure 1. Graphic distribution of divisors (<ref>) for
n=1,2,...,50 as a square matrix (left panel). Each blue square denotes +1.
In the inverse matrix (<ref>) blue square denotes +1 and red
square denotes -1 (right panel).







§ GENERAL CASE


The particular choice of the exponential function in (<ref>) is not
crucial to our reasoning. Indeed, instead of this function we can take
any regular function f(  x) provided that it has all
non-zero coefficients in its power series expansion

    f(  x)  =c_0+c_1x+c_2x^2+c_3x^3...     c_i
    ≠0 for i=1,2,3,...

Thus in general we have (up to appropriate normalizing factor)

    α_nk=.  d^n/dx^nf(
    x^k)  | _x=0



For example, taking

    f(  x)  =x/1-x=x+x^2+x^3+...

we get:

    α_nk=.
    
    
    ∑_j=1^∞
    jknx^jk-n| _x=0

or simply

    α_nk=.
    
    
    ∑_j=1^∞
    x^jk-n/(  jk-n)  !| _x=0

Taking

    f(  x)  =log(  1-x)  =-x-x^2/2-x^3
    /3-...

we get:

    α_nk=(  -1)  ^n/kn/k.
    
    
    ∑_j=1^∞
    (  -1)  ^j/jjknx^jk-n|
    _x=0



The general explicit formula for α_nk using arbitrary function f
satisfying (<ref>) is:

    α_nk=(  n/k)  !1/f^(n/k)(  0)
    .
    
    
    ∑_j=0^∞
    f^(j)(  0)  /j!jknx^jk-n|
    _x=0

where f^(j)(  0) denotes the j-th derivative of f with
respect to x taken at x=0. (If n/k in (<ref>) is non-integer
then the value of fractional derivative f^(n/k)(  0) is
unimportant since in this case the sum vanishes.)

The table below contains normalizing factors for α_nk, for several
different choices of function f(x), obtained using (<ref>
).

t]ll
f(  x)  =e^x     α_nk=n/k!1/n!.
d^n/dx^nf(  x^k)  |
_x=0

f(  x)  =ln(  1-x)     α_nk=-n/k
1/n!.  d^n/dx^nf(
x^k)  | _x=0

f(  x)  =x/1-x     α_nk=1/n!.
d^n/dx^nf(  x^k)  |
_x=0

f(  x)  =√(1+x)     α_nk=-(-2)^n/k/(
2n/k-3)  !!n/k!1/n!.  d
^n/dx^nf(  x^k)  | _x=0

f(  x)  =1/√(1+x)     α_nk=(  -1)
^n/kΓ(  1/2)  /Γ(  n/k+1/2)  n/k!1/n!.  d^n
/dx^nf(  x^k)  | _x=0

f(  x)  =(  1+x)  ^-3/2     α_nk
=(-2)^n/k/(  2n/k+1)  !!n/k!1/n!.  d^n/dx^nf(  x^k)
| _x=0

f(x)=W(x)     α_nk=(  -1)  ^n/k-1n/k
!/(  n/k)  ^n/k-11/n!.
d^n/dx^nf(  x^k)  |
_x=0

f(  x)  =1/1-x-x^2     α_nk=1/F_n/k+11/n!.  d^n/dx^nf(
x^k)  | _x=0



(W(x) is the Lambert W-function andF_n in the last row denotes the
n-th Fibonacci number.)



§ INTERPRETATION


Let us now explain in more details how it all works. The thing is that all
formulas for α_nk presented so far encode, at least to some extent,
the ancient algorithm known as the sieve of Eratosthenes.

Indeed, consider as f(x) the function f(x)=x/(1-x) and let us temporarily
restrict ourselves to the linear case:f(x)≈ x. According to the
general formula (<ref>) we have

    α_nk=1/n!.  d^n/dx^nf(
    x^k)  | _x=0=1/n!.  d^n
    /dx^nx^k| _x=0=kn.  x^k-n
    | _x=0=δ_k,n

and this produces a single line of ones on the diagonal n=k in the divisor
matrix (<ref>) – cf. Figure 2 below. This is equivalent to the
trivial statement that all integers are divisible both by one and by
themselves. Let us further consider more precise approximation f(x)≈
x+x^2. We get from (<ref>) another sequence of ones on the line
n=2k. This is equivalent to selecting all even integers n and adding to
the divisor matrix (<ref>) their divisors n/2. Taking into
account higher powers of x we select all numbers n which are multiplies
of 3,4,5,... and this adds to the matrix further lines of divisors:
n/3,n/4,n/5, respectively.

Proceeding in the same way we finally arrive at the full expansion of f(x):

    f(x)=x/1-x=
    
    
    ∑_j=1^∞
    x^j

which produces the entire sequence of lines n=jk labelled by parameter
j=1,2,3,.... In this way we have selected and visualized all
divisors for all integers. It is clear that there are certain well-defined
numbers n (marked in bold in Figure 2) which have exactly two divisors:
unity and themselves, i.e. prime numbers: 2,3,5,7,11,13,... At the same time
we see the importance of condition c_i≠0 in (<ref>) since
even a single coefficient c_i=0 would cause a skipping of certain
divisors. In view of this the characteristic function for divisors may also be
written in a very natural form as a sum over Kronecker deltas:

    α_nk=
    
    
    ∑_j=1^n
    δ_jk,n



Note that combining (<ref>), (<ref>) and (<ref>) gives:

    σ_0(n):=
    
    
    ∑_k=1^n
    α_nk=1/n!d^n/dx^n.
    
    
    ∑_k=1^∞
    x^k/1-x^k| _x=0

Hence

    ∑_k=1^∞
    x^k/1-x^k=
    
    
    ∑_n=1^∞
    σ_0(n)x^n

which is consistent with the theory of Lambert series (see e.g. <cit.>
) which is the generating function for the sequence σ_0(n) where
σ_0(n) is the total number of divisors for a given integer n.



















    < g r a p h i c s >



Figure 2. Distribution of divisors of integers computed from α_nk.
This figure illustrates how various terms in the sum (<ref>)
contribute to the whole pattern of divisors. Each term corresponds to a ray of
divisors. Rows are labelled by consecutive integers n and columns are
labelled by potential divisors k. Each colored disc means that given k
actually divides n, otherwise there is small black circle. To better
visualize the whole pattern discs are in 3 different colors and lines
connecting them are drawn. Of course, above the diagonal (k>n) there can't
be any divisors.







§ CONCLUDING REMARKS


A few elementary comments at the end of this note. As we have seen, all
divisors k of integers n lie on rays passing through the origin of the
coordinate system on the (n,k) plane and are labelled by an integer
parameter j=1,2,3...

    n=jk

We have also seen that this simple condition has a natural interpretation
since j may be identified with the exponent in x^j in the expansion
(<ref>). The key thing is that these rays must pass through certain
points of an integer lattice and only then a potential divisor can be an
actual divisor. For large n these rays typically get closer and closer to
one another. Therefore we qualitatively see why it is so difficult to
factorize large integers.

Moreover, numerical experiments suggest that all divisors lie on
countable families of parabolas passing through the origin (see Figures 3, 4
and 5 below). These parabolas are "quantized" in the sense that each family is
characterized by two discrete parameters μ=1,2,3... and ν=1,2,3... and
inside any family parabolas are labelled by another integer parameter i:

    g_i^(μν)(k)=-μ/νk^2+i/νk

Careful simulations using Mathematica revealed that parameter i assumes
equidistant values with integer constant step:

    δ=(μ,ν)

starting from i=μ+ν where  denotes greatest common divisor, i.e.
i=μ+ν, μ+ν+δ, μ+ν+2δ,...













    < g r a p h i c s >



Figure 3. Various families of parabolas (<ref>) for μ=1,2,3 and
ν=1,2,3. Step δ (<ref>) described in the main text is also
indicated.



















    < g r a p h i c s >



Figure 4. Family of parabolas (<ref>) for μ=1 and ν=1
(red),2 (orange),3 (green),and 4 (cyan) for n<100. For clarity of
the plot parameter i assumes only 50 consecutive values. Prime numbers
among ns are indicated by vertical lines.



















    < g r a p h i c s >



Figure 5. Family of parabolas (<ref>) for μ=1 and ν=1
(red),2 (yellow) and 3 (green) around n=740. For clarity of the plot
parameter i assumes only 5 consecutive values. Prime numbers among ns
are indicated by vertical lines.





As far as I am aware the unexpected parabolas in the distribution of divisors
have been independently noticed by Jeffrey Ventrella (see his popular book
<cit.>, page 33) but with no quantitative considerations.

Finally, it should be stressed that, unfortunately, expressions presented in
this note do not tell us much about distribution of primes. They are even not
very suitable for numerical calculations for large n therefore may be
treated merely as a curiosity. Nevertheless, we have shown some unexpected
relationship between number theory and calculus.

Acknowledgments. The author would like to thank Prof. Jeffrey
Lagarias for his encouragement and several suggestions and to Prof. Andrzej
Schinzel for several remarks.

The results presented in this paper were inspired by experimenting
with Wolfram Mathematica. Also all calculations were checked using this
powerful software.

9                                                                                                
Inverse sequenceOn-Line Encyclopedia of Integer Sequences,
sequence number A054525.

ApostolTom M. Apostol, Modular Forms and Dirichlet Series
in Analysis, 1976, Springer-Verlag.

CoxDavid N. Cox, Visualizing the Sieve of Eratosthenes,
Notices of the AMS, vol. 55, nr. 5, May 2008, p. 579-582.

MillerRossKennet S. Miller, Bertram Ross, An Introduction
to the Fractional Calculus and Fractional Differential Equations, 1993, John
Wiley and Sons.

RedhefferRaymond M. Redheffer, Eine explizit lösbare
Optimierungsaufgabe, Internat. Schriftenreihe Numer. Math. vol. 36, 1977.

TrottMichael Trott, The Mathematica GuideBook for
Programming, 2004, New York: Springer-Verlag.

VentrellaJeffrey J. Ventrella, Divisor Drips and Square
Root Waves – Prime Numbers are the Holes in Complex Composite Number
Patterns, 2010, Eyebrain Books (book web site: www.divisorplot.com).



