\documentclass[12pt,reqno]{article}
\usepackage{color}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
%\definecolor{webgreen}{rgb}{0,.5,0}
%\definecolor{webbrown}{rgb}{.6,0,0}
%\usepackage{psfig,epsf,latexsym}
\usepackage{amsthm,amsfonts,amssymb,amsmath,epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.7in}
\def\divides{\ | \ }
\def\lcm{{\rm lcm}}
\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/
~njas/sequences/eisA.cgi?Anum=#1}{
\underline{#1}}}
% \renewcommand{\baselinestretch}{1.4}
\def\C{{\mathbb C}}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{conjecture}[theorem]{Conjecture}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\begin{center}
\vskip 1 cm
{\LARGE\bf Tau Numbers: A Partial Proof of a
\\
\ \\
\vskip -.2in
Conjecture and Other Results}
\vskip 1.5 cm
\large Joshua Zelinsky\\
The Hopkins School\\
New Haven, CT 06515 \\
USA\\
\medskip
Email: {\tt Lord\_Bern@hotmail.com}
\end{center}
{\bf Abstract.}
A positive $n$ is called a {\sl tau number} if $\tau(n) \divides n$, where $\tau$
is the number-of-divisors function.
Colton conjectured that
the number of tau numbers $\leq n$
is at least ${1 \over 2} \pi(n)$.
In this paper I show that Colton's
conjecture is true for all sufficiently
large $n$.
I also prove various other results about tau numbers and their
generalizations .
\section{Introduction}
Kennedy and Cooper \cite{Kennedy} defined a positive integer to be a
{\sl tau number} if $\tau(n) \ | \ n$, where $\tau$ is the
number-of-divisors function. The first few tau numbers are
$$1, 2, 8, 9, 12, 18, 24, 36, 40, 56, 60, 72, 80, \ldots;$$
it is Sloane's sequence \seqnum{A033950}.
Among other things, Kennedy and Cooper
showed the tau numbers have density zero.
The concept of tau number was rediscovered by Colton, who called
these numbers {\sl refactorable} \cite{Colton}.
This paper is primarily concerned with two conjectures made
by Colton. Colton conjectured that the number of tau numbers less than or
equal to a given $n$ was at least half the number of primes less than or
equal
to $n$. In this
paper I show that Colton's conjecture is true for all
sufficiently large $n$
by proving a generalized version of the conjecture. I calculate
an upper bound for counterexamples of $7.42 \cdot 10 ^{13} $.
Colton also
conjectured that there are no three consecutive tau numbers and I show
this
to be the case. Other results are also given, including the properties of
the tau numbers as compared to the primes. Various generalizations of the
tau
numbers
are
also discussed.
\section{Basic results}
\bigskip
\noindent{\bf Definitions.}
Let $\pi(n)$ be the number of primes less than or equal to $n$.
Let $T(n)$ be the number of tau numbers
less than or equal to $n$.
\bigskip
Using this notation,
Colton's conjecture becomes: $T(n) \geq \pi(n)/2$ for all $n$.
Before we prove a slightly weaker form of this
conjecture, we mention some
following minor properties of the tau numbers.
Throughout this paper, the following basic result
\cite[Theorem 273]{Hardy} is used
extensively:
\begin{proposition}
If $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ then
$\tau(n) = (a_1+1)(a_2+1)(a_3+1)\cdots(a_k+1)$.
\label{hw}
\end{proposition}
The next five theorems are all due to Colton.
\begin{theorem}
Any odd tau number is a perfect square.
\label{thm1}
\end{theorem}
\begin{proof}
Assume that $n$ is an odd tau number. Let $n = p_1^{a_1} p_2^{a_2} \cdots
p_k^{a_k} $. By Proposition~\ref{hw} and the definition of tau number
$(a_1+1)(a_2+1)(a_3+1)\dots(a_k+1) \ |\ n $.
Therefore for any $0* 3$, the number
$36pq$ is a tau number.
\label{lemma1}
\end{lemma}
\begin{proof}
By the multiplicative property of the tau function,
$\tau(36pq)= \tau(4) \tau(9) \tau(p) \tau(q) = 3 \cdot 3 \cdot 2 \cdot 2 =
36$.
\end{proof}
\begin{lemma}
%Lemma 2:
Let $k$ be an integer $\geq 1$. Then the number of integers $\leq n$
of the form $kp$, where $p$ is prime, is
asymptotic to $n/ (k \log n )$. Similary, for any fixed integer $a \geq
1$
the numbers of integers $\leq n$ of the form $kp^a$
is asymptotic to $((n/k)^{1/a})/\log(n)$.
\label{lemma2}
\end{lemma}
\begin{proof}
Both these formulas follow easily from the prime number theorem.
\end{proof}
\begin{lemma}
%Lemma 3:
Let $k$ be a positive integer.
Then the number of numbers $\leq n$
of the form $kpq$, where $p, q$ are distinct primes, is
asymptotic to $(n \log\log n)/(k\log n)$.
\label{lemma3}
\end{lemma}
\begin{proof}
We use a Theorem of Hardy and Wright \cite[Thm.\ 437]{Hardy}, which
states that the number of
squarefree numbers
less than $n$ with $k$ prime factors, $k \geq 2$ is asymptotic to
$\frac{n (\log\log n)^{k-1}}{(k-1)!\log n}$. Setting $k=2$ and using the
same
techniques as in the proof for Lemma~\ref{lemma2} yields the desired
result.
\end{proof}
\begin{lemma}
% Lemma 4:
The numbers of tau numbers $\leq n$ of the form $36pq$ with $p, q$
distinct primes $> 3$ is asymptotic to
$(n \log\log n)/(36 \log n)$.
\label{lemma4}
\end{lemma}
\begin{proof}
By Lemma~\ref{lemma3}
the number of positive integers $\leq n$ of the form $36pq$ is
asymptotic to
\begin{equation}\label{eq2}
\frac{n \log \log n }{36 \log n}
\end{equation}
The number of tau numbers of the form $36pq$ with $p, q$ prime numbers
$> 3$ is the number of numbers
of the form $36pq$ minus the number of numbers of the
form $36 \cdot 2 \cdot p$ or
$36 \cdot 3 \cdot p$.
Thus, using \ref{eq2}, together with Lemma~\ref{lemma3} the number
of such numbers is asymptotically
\begin{equation}\label{eq3}
\frac{n \log\log n}{36\log n}- \frac{n}{72 \log n } -\frac{n}{108\log n} -
\end{equation}
which is asymptotic to the first term.
\end{proof}
\begin{lemma}
%Lemma 5:
For any fixed real number $r < 1$ we have
$T(n)>\frac{rn\log\log n}{36\log n}$ for all $n$ sufficiently large.
\label{lemma5}
\end{lemma}
\begin{proof}
This inequality follows from Lemmas~\ref{lemma4} and \ref{lemma1}.
\end{proof}
\begin{theorem}
For any real number $k$ we have $T(n) > k\pi(n)$ for all $n$
sufficiently large.
\label{thm7}
\end{theorem}
\begin{proof}
Clearly for any positive $r < 1$, and any $k$, for all sufficiently large
$n$,
\begin{equation}\label{eq5}
\frac{rn\log \log n}{36\log n} >kn/\log n.
\end {equation}
Since $\pi(n) \sim n/\log n$, for all sufficiently large $n$,
$\frac{rn \log\log n}{36\log n} >k\pi(n)$.
By applying Lemma~\ref{lemma5}, we conclude that for all
sufficiently large $n$,
$T(n) > k\pi(n)$.
\end{proof}
\begin{corollary}
%Corollary 1:
\end{corollary}
For any $b>0$ there are at most a finite number of integers $n$ such that
$T(n)> b\pi(n)$.
\begin{proof}
This result follows immediately from Theorem~\ref{thm7}.
\end{proof}
\begin{corollary}
%Corollary 2:
There are at most a finite number of integers
$n$ such that $ T(n) < .5\pi(n)$.
\end{corollary}
\begin{proof}
Let $b=.5$ in the above corollary.
\end{proof}
\bigskip
Theorem~\ref{thm7} also implies that $T(n) >\pi(n)$ for all
sufficiently large $n$.
Colton gave a table of $T(n)$ showing
that $T(10^7) $ is about $.59\pi(n)$. So
$T(n)$ must not drastically exceed $\pi(n)$ until $n$ becomes very large.
This is a good example of the law of small numbers. In fact, we can
construct an even better example of the law of small numbers.
\bigskip
\noindent{\bf Definition.}
An integer $n$ is {\sl rare} if $\tau(n) \ | \ n $, $\tau(n)\ | \ \phi(n)$
and
$\tau(n)\ | \ \sigma(n)$, where $\phi(n)$ is
the number of integers less than or
equal to $n$ and relatively prime to $n$, and $\sigma(n)$ is the sum of
the
divisors of $n$.
\bigskip
Let $R(n)$ be the number of rare numbers $\leq n$. We can use a
construction
similar to the one above to show that if $p, q$ are distinct primes,
not equal to $2$,$3$ or $7$, then $672pq$ is rare. Using similar logic
to
that above, we can conclude for any $k$, for all sufficiently large $n$,
$R(n) > k\pi(n)$. Thus, although there are only two rare numbers less than
$100$ (namely, $1$ and $56$) and there are $25$ primes less than $100$,
for all
sufficiently large $n$, $R(n) > \pi(n)$ .
It would be interesting to establish
a good upper bound beyond which this inequality always holds. In the above
construction,
we have "cheated" slightly since $n$ such that $\tau(n)\ | \ \sigma(n)$
have density 1.
Note that we could have proven tau-prime density result result proving
that all numbers of the form $kpq$ for any $k$ exceeds the density of
the primes just like those of the form $36pq$ and then looking at the
subset
of tau numbers of the form $36pq$. There are other sequences of tau number
that
could have been used to the same effect, such as those of the form $80pqr$
where $p$, $q$ and $r$ and are distinct odd primes not equal to $5$. It is
not difficult to generalize the above theorem to show that for any $k$,
\begin{equation}\label{eq6}
((n\log\log n)^k)/\log n = o(T(n)).
\end{equation}
Finding an actual asymptotic formula for $T(n)$ is more difficult. We can
address this issue with certain heuristics. We know that
$\tau(n)$ is of average order
$\log n$. Since $n$ is a tau number when $n \bmod \tau(n) = 0$ and $n
\bmod
\tau(n)$ can have
$\tau(n)$ values, we would expect the probability of a random integer to
be
a tau number to be $1/\log(n)$.
However, integrating this yields $n/\log n$ as the
asymptotic value, which is too low even if we multiply it by a constant.
However, almost all integers have about ${\log n}^{\log 2}$ divisors
\cite[p.\ 265]{Hardy}, and a
few integers with large tau values bring up the average. If we use the
same
logic as above and note that almost all tau numbers are divisible by 4, it
makes sense to take 1/4th of the integral of $(\log n)^{-\log 2}$.
Thus we arrive
at the following conjectured relation:
\begin{conjecture}
%Conjecture 1:
\begin{equation}
T(x) \sim (1/4) \int_3^x {\log u}^{-\log 2} du.
\end{equation}
\end{conjecture}
This conjecture gives an approximate values of $42854$ for $T(10^6)$ and
$381659$ for $T(10^7)$. Colton's table gives $T(10^6) = 44705$ and
$T(10^7) = 394240$. Our heuristic approximation
seems to slightly underestimate
the actual values, being $95.8\%$ and $96.8\%$ of the actual values,
respectively. This
underestimate is expected
since the integral approximation ignores the tau numbers
congruent to $1$ or $2 \bmod 4$. In fact, we conjecture that for all
sufficiently large $n$ the integral underestimates $T(n)$. Since the
relationship between
$\tau(n)$ and $(\log n)^{\log 2}$ is weak,
it seems much safer to conjecture the weaker:
\begin{equation}
\log T(x) \sim \log \left( {1 \over 4} \int_3^x (\log u)^{-\log 2} du \right).
\end{equation}
It is possible, using the known bounds for the various asymptotic
formulas here to obtain an actual upper bound above which Colton's
conjecture must be true. It is not difficult, although computationally
intensive, to use a few different generators along with $36$ to obtain a
bound of $10^{37}$. However, using a more general method it is possible to
lower the bound to slightly over $7 \cdot 10^{13}$.
\begin{lemma}
%Lemma 6:
$2 \ | \ n/\tau(n)$ iff for
any prime $p$ such that $p$ does not divide $n$, $np$ is a
tau number.
\label{lemma6}
\end{lemma}
Example: $2 \ | \ 8/\tau(8) = 8/4 = 2$ and $8p$ is a tau number for all
odd
primes $p$.
The proof is left to the reader.
\bigskip
\noindent{\bf Definition.} A tau number $n$ such that
for any prime $p$, if $p$ does not divide $n$ then
$np$ is a tau number, is called a {\sl $p$-generator}. Any tau number
of the form $np$ is said to be
{\sl $p$-generated} by n.
Thus, in the example above, $8$ is a $p$-generator.
Thus Lemma~\ref{lemma6} can be
restated as follows:
$n$ is a $p$-generator iff $2\ | \ n/\tau(n)$. In what follows,
both forms of this
lemma are used interchangeably.
\bigskip
\noindent{\bf Notation.}
Let $\omega(n)$ denote the number of distinct prime factors of $n$.
Let $g(n)$ denote the largest prime factor of $n$.
Let $G(n)= n(n+1)/2$.
Let $P_n$ denote the $n$th prime, with $P_1 = 2$.
\begin{lemma}
%Lemma 7:
Let $k$ be a $p$-generator. The number of tau numbers $\leq n$
of the form $kp$
is at least
$\pi(n/k) - \omega(n).$
\label{lemma7}
\end{lemma}
\begin{proof}
Left to the reader.
\end{proof}
\begin{lemma}
%Lemma 8:
If $a_1,a_2, \dots a_s$ are $p$-generators, then for any $n$ the
number of tau numbers $\leq n$ $p$-generated by any $a_i$ is at least
\begin{equation}\label{eq7}
\sum_{i=1}^s \pi(n/a_i)-\pi(g(a_i)).
\end{equation}
\label{lemma8}
\end{lemma}
\begin{proof} The proof follows from Lemma~\ref{lemma6}
when we observe that for any
$a_i,a_j$ where
$k=\pi(g(a_i))+1$ and $m=\pi(g(a_j))+1$,
the sets $\lbrace a_iP_k,a_iP_{k+1}, a_iP_{k+2}, \ldots \rbrace$ and
$\lbrace a_jP_m, a_jP_{m+1},a_j P_{m+2}, \ldots \rbrace$
have no common elements.
\end{proof}
\begin{lemma}
%Lemma 9:
If $a_1,a_2,a_3,\dots$ are $p$-generators then for any $n$ the
number of tau numbers $\leq n$ $p$-generated by any $a_i$ is at least
$A\pi(n)
-B$ where
$A=\sum_{i=1}^k 1/a_i$ and
$B=\sum_{i=1}^k (\pi(g(a_i))+1)$.
\label{lemma9}
\end{lemma}
\begin{proof}
This proof follows immediately from Lemma~\ref{lemma7} since each summand
in $A$ introduces
an error of at most $1$.
\end{proof}
\begin{theorem}
For all $n>7.42 \cdot 10^{13}$ we have $T(n) > \pi(n)/2$.
\label{thm8}
\end{theorem}
\begin{proof}
It has been shown by Dusart \cite{Dusart} that for all
$n>598$, the inequality
$$(n/\log n ))(1+.992/\log n ) <\pi(n)<(n/\log n)(1+1.2762/\log n)$$
holds.
We use all the $p$-generators less than or equal to $28653696$ together
with Lemma~\ref{lemma9} to
obtain a lower bound for the number of tau numbers, and then
demonstrate that for all $n$ greater than $7.42 \cdot 10^{13}$, this
exceeds
$.5(n/\log n )(1+1.2762/\log n)$ and thus exceeds $.5\pi(n)$. Using a
simple
computer program, it is not difficult to calculate that there are exactly
$413980$ $p$-generators less than
$28653696$. Their $A$ value as in Lemma~\ref{lemma9} is over $.508.$
It is not difficult
to see that
\begin{eqnarray*}
B &<& G(\pi(413980/36)) +G(\pi(413980/80))+G(\pi(413980/96))
+(413980-\pi(413980/36) \\
&-& \pi(413980/80)-\pi(413980/96))-\pi(413980/128).
\end{eqnarray*}
Calculating the relevant values and evaluating the above expression
yields
$B < 8694520815$.
Thus, for all $n>598 \cdot28653696$, we have $T(n) >
.508(n/\log n)(1+.992/\log n)-8694520815$.
For all $n>10^{13.87}, 508(n/\log n)(1+.992/\log n)-8694520815 >
.5(n/\log n)(1+1.2762/\log n)$.
Since $10^{13.87}< 7.42 \cdot 10^{13}$ we conclude that for all $n>7.42
\cdot 10^{13}$, we have
$T(n)>.5\pi(n)$.
\end{proof}
\bigskip
The high density of the tau numbers
and their relationship to the primes motivates
the comparison of the two types of integers.
\begin{theorem} The sum of the reciprocals of the tau numbers diverges.
\label{thm9}
\end{theorem}
\begin{proof} The result follows immediately by observing that $8$ is a
$p$-generator and that the sum of the reciprocals of the primes diverges.
\end{proof}
\bigskip
There is a famous still unsolved conjecture, by Polignac, that for any
positive even integer $k$, there exist primes $p, q$ such that $k=p-q$
\cite{Ribenboim}. It seems reasonable to make an identical conjecture
about
the tau numbers. Indeed, the existence of infinitely many
odd tau numbers makes one wonder
whether every positive integer is the difference of two tau numbers.
However,
there
are some odd integers which are not the difference of two tau numbers
despite
the
fact that the density of the tau numbers is much higher than that of the
primes.
\begin{theorem}
There do not exists tau numbers $a,b$ such that $a-b=5$.
\label{thm10}
\end{theorem}
\begin{proof}
Suppose, contrary to what we want to prove, that
there exist tau numbers $a, b$ such that
$a-b=5$.
By Theorem~\ref{thm6} we know
that every tau number is congruent to $0,1,2$ or $4$ (mod 8).
Thus, we have
$b \equiv 4$ (mod 8) and $a \equiv 1$ (mod 8).
Hence $4$ is the highest power of two which
divides $b$. Thus $\tau(4) = 3 \ | \ \tau(b)$, and since
$\tau(b) \ | \ b$ we get $b \equiv 0$ (mod 3).
Then $a \equiv 2$ (mod 3),
which is impossible since $a$ is an odd tau number and hence a square.
\end{proof}
\bigskip
Goldbach made two famous conjectures about the additive properties of the
primes. Goldbach's strong conjecture is that any even integer greater than
$4$ is the sum of two primes. Goldbach's weak conjecture is that every odd
integer greater than $7$ is the sum of the three odd primes. It is easy to
see that the weak conjecture follows from the strong
conjecture \cite{Ribenboim}.
However,
Colton's congruence results of Theorem~\ref{thm6}
imply that any $n \equiv 7$ (mod 8) cannot be
the sum of two tau numbers.
The following theorems and the next conjecture are the tau equivalents of
Goldbach's conjecture.
\begin{theorem}
\begin{itemize}
\item[(a)] If Goldbach's weak conjecture
is true than any positive integer can be
expressed as the sum of $6$ or fewer tau numbers.
\item[(b)] If Goldbach's strong conjecture is true than every positive
integer
is
the sum of $5$ or fewer tau numbers.
\end{itemize}
\label{thm11}
\end{theorem}
\begin{proof}
(a) Assume Goldbach's weak conjecture. Let $A$ be the set of
integers $n$ such that $8n$ is a tau number or $n = 0$. Consider $x = 8k$
for
some
odd $k > 7$. Since every odd prime is an element of $A,$ $k =a_1 + a_2
+a_3$
for some $a_1, a_2, a_3$ element $A$. So $8k = 8a_1+ 8a_2 +8a_3$. Since
$8k =
8$ mod 16, we conclude that for any $x \equiv 8$ mod 16, $x$ is the sum of
at
most
three tau numbers. It is easy to see from this result and the fact that
$1,2,8,9,12$ are all tau, that any integer greater than $56$ can be
expressed as the sum of $6$ or fewer tau numbers. It is easy to verify
that
every
integer under $56$ can be expressed as the sum of $6$ or fewer tau
numbers.
Thus,
if Goldbach's weak conjecture is true than every integer is the sum of $6$
or fewer tau numbers.
Case (b) follows by similar reasoning.
\end{proof}
\begin{theorem}
For all sufficiently large $n$, $n$ can be expressed as the sum of $6$ or
fewer tau numbers.
\label{thm12}
\end{theorem}
\begin{proof}
This result follows from applying Vinogradov's famous result that every
sufficiently large odd integer is expressible as the sum of three or fewer
primes and using the same techniques as in the previous theorem.
\end{proof}
\bigskip
The techniques in the previous theorems can also be used to prove the
following corollary.
\begin{corollary}
%Corollary 3:
If Goldbach's weak conjecture is true than any positive integer
not congruent to $7$ mod 8 can be expressed as the sum of $5$ or fewer tau
numbers.
If Goldbach's strong conjecture is true than every positive integer not
congruent to $7$ mod 8 is the sum of $4$ or fewer tau numbers.
\end{corollary}
Note that since the set $A$ introduced in the proof of Theorem~\ref{thm11}
contains many elements other than the primes, even if
either the weak or the strong Goldbach conjectures fail to hold,
it is still very likely that
all integers can be expressed as the sum of six or fewer tau numbers.
We make the following
\begin{conjecture}
%Conjecture 2:
Every positive integer is expressible as the sum of $4$ or
fewer tau numbers.
\end{conjecture}
It seems that the above conjecture cannot be proven by
methods similar to those used in Theorem~\ref{thm11}.
\bigskip
For any $n$, Bertrand's postulate states that there is a prime between $n$
and
$2n$. The equivalent for tau numbers is the next theorem:
\begin{theorem}
For any integer $n>5$ there is always a tau number between $n$ and $2n$.
\label{thm13}
\end{theorem}
\begin{proof}
This result follows immediately from the fact that $8$ is a
$p$-generator.
\end{proof}
\bigskip
Another unsolved problem about primes is whether there is always a prime
between $n^2$ and $(n+1)^2$.
The fact
that the tau numbers have a much higher density than the primes motivates
the following conjectures:
\begin{conjecture}
%Conjecture 3:
For any sufficiently large integer $n$, there exists a tau number
$t$ such that
$n^2 0$ there exist infinitely many
$n$ such that $n$
is a $(a_1,a_2 \dots a_k)$-generator.
\item[(c)] For any tau number
$n>2$ there exist $a_1,a_2,a_3 \dots a_k$ such that $n$ is
an $(a_1,a_2,a_3 \dots a_k)$-generator. In particular, $n$ is a
$(n/\tau(n)
-1)$-generator.
\item[(d)] Apart from the order of the exponents any given tau number
has $\sum_{d|n/\tau(n)}
h(d)$ generators.
\item[(e)] If for some $a_1,a_2,\dots a_k$ $n$ is an
$(a_1,a_2,\dots, a_k)$-generator
then for any $0 .5n^{1/2}$.
\label{lemma10}
\end{lemma}
\begin{proof}
This follows immediately from Lemma~\ref{lemma92}.
\end{proof}
\begin{lemma}
%Lemma 11:
For any real number $r$, if $n/\tau(n) \leq r$ then $n\leq 4r^2$.
\label{lemma11}
\end{lemma}
\begin{proof}
This follows immediately Lemma~\ref{lemma10}.
\end{proof}
\bigskip
The next lemma is easy to prove and the proof is omitted.
\begin{lemma}
%Lemma 12:
For any prime $p$, tau number $n$, and integer $k \geq 1$,
if
$p^{p^k -1}\ |\ n/\tau(n)$ then $p^{p^k} \ | \ n$.
\label{lemma12}
\end{lemma}
\begin{theorem}
There does not exist $n$ such that $t(n) = 18$.
\label{thm16}
\end{theorem}
\begin{proof}
By Lemma~\ref{lemma11} we merely need to verify the claim for $n \leq
1296$.
Using Lemma~\ref{lemma12} we need only to check the multiples of $108$
which is easy to do.
\end{proof}
Kennedy and Cooper's result that the tau numbers have density $0$
\cite{Kennedy}, along with
Lemma~\ref{lemma11}, motivates the following conjecture:
\begin{conjecture}
%Conjecture 7:
There exist infinitely many positive integers $k$ such that for all $n$,
$t(n)
\not= k$.
\label{conjecture7}
\end{conjecture}
We can prove a much weaker result than the above conjecture. We
show that there are integers which are not in the range of $t(2n+1)$ .
First we need two lemmas corresponding to the earlier lemmas.
\begin{lemma}
%Lemma 13:
For any odd integer $n,$ $\tau(n) \leq \lceil n^{1/2} \rceil$.
\label{lemma13}
\end{lemma}
\begin{proof}
This follows from a modification of Lemma~\ref{lemma9}.
\end{proof}
Lemma~\ref{lemma13} leads directly to Lemma~\ref{lemma14}:
\begin{lemma}
%Lemma 14:
For any odd integer $n$, $ t(n) \geq \lfloor n^{1/2} \rfloor$.
\label{lemma14}
\end{lemma}
\begin{proof}
This follows from Lemma~\ref{lemma13}.
\end{proof}
\begin{theorem} There exist infinitely many odd integers $k$ such that
$t(n) \not= k$ for
all odd $n$. Specifically, whenever $k$ is an odd prime greater than $3$,
$t(n) \not= k$ for all odd $n.$
\label{thm17}
\end{theorem}
\begin{proof}
Assume that for some prime $p > 3$, $t(n) =p$. So by
Lemma~\ref{lemma14}, $p >
\lfloor n^{1/2} \rfloor$. So $p+1 > n^{1/2}$ and thus $p^2+ 2p + 1 \geq
n$. Now
since
$n$ is an odd tau, $n$ is a perfect square. So $p^2 \ | \ n$ . But $n \leq
p^2 +
2p
+ 1$. Thus $n=p^2$ which is impossible.
\end{proof}
Using a similar method as the proof of the last theorem, we get the
following slightly stronger result:
\begin{theorem}
Let $p$ be a prime $> 3$. Let $n$ be a tau number
such that $t(n) =p$. Then $4|n$.
\label{thm18}
\end{theorem}
Note that since almost all tau numbers are divisible by $4$,
the above result is a
far cry from Conjecture~\ref{conjecture7}.
In fact, for any odd prime $p$ we have $t(8p)=p$.
Colton also has made the conjecture that for any $n>2$, the number
$n!/3$ is always a tau number.
The following heuristic suggests a related conjecture:
\begin{conjecture}
%Conjecture 8 :
For any positive integers $a, b$ with $a$ odd, there exists an integer
$k$ such that
$ (a/b)n!$ is a tau number for all $n > k$.
\end{conjecture}
We give a heuristic reason to believe this conjecture.
Let $a$ and $b$ be integers. Consider some $n$ much larger than
$a$ and $b$. Now on average, for some prime $p$, it is easy to see that
the mean number of times $p$ appears in the factorization of $n$ is
about $1/(p-1)$. For
large $n$, the change made by $a$ and $b$ in the number of factors is
small. So for any prime $p$ in the factorization of $(a/b)n!$, $p$ is
raised
to a power approximately equal to $n/(p-1)$.
and there are about $n/\log n$ primes $\leq n$. Hence
the highest power of $p$ dividing
$\tau((a/b)n!))$ is about $n/((p-1)\log n)$.
For all sufficiently large $n$,
$n/(p-1)$ is much larger than $n/((p-1)\log n)$.
Since every prime exponent of $\tau((a/b)n!))$ is less than the
corresponding
exponent for $(a/b)n!$ we conclude that
$\tau((a/b)n!)) \ | \ (a/b)n!$.
\bigskip
Note: The reason $a$ must be odd in the above conjecture is subtle. Let
$n
= 2^k$. It is not difficult to see that
$2^{n-1}\ |\ n!$. Thus if $a$ has some power of $2$ dividing it than one
can
force the power of $2$ in
$an!$ to be slightly over $n$, such as $2^{n+2}$, in which case
$(2^k)+3|\tau(an!)$ and $2^k+3$ may be prime infinitely often, in which
case
$\tau(an!)$ does not divide $an!$ for any such $k$. Examples other than
$2^k+3$ would also suffice. It is easy to see that this problem only
arises
with $2$ and not any other prime factor.
We can prove a large portion of this conjecture. We first require a few
definitions.
\bigskip
\noindent{\bf Definition.}
Let $\nu_p(n)$ denote the largest integer $k$ such that $p^k \ | \ n$.
\begin{lemma}
%Lemma 15:
$n$ is a tau number iff for any prime $p, \nu_p(\tau(n)) \leq \nu_p(n)$.
\label{lemma15}
\end{lemma}
\begin{proof}
This follows immediately from the definition of $L$.
\end{proof}
\begin{lemma}
%Lemma 16:
$\lfloor n/p \rfloor \leq \nu_p(n!) \leq \lceil n/(p-1) \rceil$.
Furthermore,
$\nu_p(n!) \sim n/(p-1)$.
\label{lemma16}
\end{lemma}
\begin{proof}
The proof is left to the reader.
\end{proof}
\begin{lemma}
% Lemma 17:
For any positive integers $a$ and $b$, and prime $p, \nu_p((a/b)n!)
\sim n/(p-1)$.
\label{lemma17}
\end{lemma}
\begin{proof}
Let $a$ and $b$ be positive integers and $p$ prime. Without loss of
generality assume $\gcd(a,b)=1$.
For all $n$,
$\nu_p(n!) - \nu_p(b) \leq \nu_p((a/b)n!) \leq \nu_p(n!)+\nu_p(a)$.
Now
applying Lemma~\ref{lemma16},
and noting that $\nu_p(b)$ and $\nu_p(a)$ are constant with
respect to $n$, we conclude that $\nu_p((a/b)n!) \sim n/(p-1)$.
\end{proof}
\begin{theorem}
Let $a$ and $b$ be positive integers, and $p$ prime. For all sufficiently
large $n$
the highest power of $p$ that divides $\tau((a/b)n!)$ also
divides $(a/b)n!$.
That is,
$\nu_p(\tau((a/b)n!))\leq \nu_p((a/b)n!)$.
\label{thm19}
\end{theorem}
\begin{proof}
Let $a$ and $b$ be positive integers and let $p$ be a prime.
Without loss of
generality assume $\gcd(a,b)=1$.
We thus need to find, for all sufficiently large $n$,
an upper bound $U_p (n)$
for $\nu_p(\tau((a/b)n!))$ and show that there
is a constant $k<1$ such that for all sufficiently large $n$,
the inequality $U_p (n)/(n/p) < k$ holds.
We consider two cases: $p=2$ and $p>2$.
Case I: $p=2$. Thus we need to find an upper bound $U_2(n)$ for
$\nu_2(\tau((a/b)n!))$ such that
$U_2(n)/(n/p) < k$ for all sufficiently large $n$ and some constant
$00$ and all sufficiently large
$n$,
\begin{equation}\label{eq11}
\nu_2(\tau((a/b)n!)) < \frac{(1+\epsilon)(n\log_2 n)}{2\log n} +
\frac{(1+\epsilon)n} {2\log n},
\end{equation}
which, when all the logarithms are made natural, becomes:
For any $\epsilon
>0$ and all sufficiently large $n$,
\begin{equation}\label{eq12}
\nu_2(\tau((a/b)n!)) \leq \frac{(1+\epsilon)n}{2\log 2}
+\frac{(1+\epsilon)n}{2\log n}
\end{equation}
Now fix $\epsilon$ as some number less than $2\log2 -1$and let such a
resulting function be $U_2(n)$. It is easy to see that the function
satisfies the desired inequality.
Case II: Let $p> 2$. Using similar logic to that used in the earlier case
we conclude that for any $\epsilon >0$ and all sufficiently large $n$
\begin{equation}\label{eq13}
\nu_2(\tau((a/b)n!)) \leq \frac{(1+\epsilon)(n+p)(\log_p n)}{p
\log((n+p)/p)}
\leq \frac{(1+\epsilon)(n+p)}{p\log p}
\end{equation}
Fixing $\epsilon$ as some number less than $p\log p -1$ and making the
rightmost part of (\ref{eq13}) equal to $U_p
(n)$ gives the desired result.
\end{proof}
Note that one could use the earlier cited bounds of Dusart to make the
above proof
constructive.
\section{Generalizations}
It is possible to generalize the concept of tau number. First consider
that
the definition of tau number
is equivalent to $n \bmod \tau(n) =0$. We now say that $n$ is
a tau number relative to $k$ if $n \bmod \tau(n) =k$.
Of course, $k=0$ gives the ordinary tau numbers and it is
easy to see that every odd prime is a tau number relative
to $1$. Also it is easy to see that any
$n$ is a tau number relative to $k$,
for some $k$. The main result about integers which are tau numbers
relative
to $k$ is the following theorem:
\begin{theorem}
For any odd $k$ there exists an infinitely many
$n$ such that $n$ is a tau number relative to
$k$.
\label{thm20}
\end{theorem}
\begin{proof}
Let $k$ be an odd integer. We claim that there exist arbitrarily large
distinct primes, $p$, $q$ and $r$ such that $p^{r-1} q \bmod
\tau(p^{r-1}q) =
k$. This is equivalent to showing that $p^{r-1}q \equiv k$ (mod $2r$). By
Fermat's
Little Theorem, $p^{r-1} \equiv 1$ (mod $r$). Thus we merely need to show
that
there
exist arbitrarily large primes $q$ such that $q \equiv k$ (mod $2r$),
which
follows
immediately from Dirichlet's theorem about primes in
arithmetic progressions.
\end{proof}
I make the following conjecture.
\begin{conjecture}
%Conjecture 10:
For any $k$, there exist infinitely many $n$ such that $n$ is
a tau number relative to $k$.
\end{conjecture}
It is not difficult to prove many special cases of this conjecture $k$
where
some $p$ is assumed not to divide $k$, as in Theorem~\ref{thm19}. In fact
we shall prove the
above conjecture by examining a larger generalization:
Let $Q(n)$ be a polynomial
with integer coefficients.
An integer $n$ is said to be a tau number
relative to $Q(n)$ if $\tau(n) \ | \ Q(n)$.
In this generalization, tau
numbers are the case where $Q(n) =n$.
Clearly the above conjecture follows from the next theorem:
\begin{theorem} For any $Q(n)$ with integer coefficients, there exist
infinitely many $n$ such that
$\tau(n) \ | \ Q(n)$.
\label{thm21}
\end{theorem}
\begin{proof}
Without loss of generality, assume the leading coefficient of $Q(n)$ is
positive. If the constant term is $0$ then any tau number is a
tau number relative to $Q(n)$.
So assume the constant term is non-zero. Chose some $c$ such that
$Q(c)\geq 1$ and
$(Q(c),c)=1$.
Now by Dirichlet's theorem there exist
infinitely many
primes $p$ such that $p \equiv c$ (mod $Q(c)$). For any such $p$,
$p^{Q(c)-1}$ is a tau number for $Q(n)$ since $\tau(p^{Q(c)-1}) = Q(c)$ and
$Q(c) \ | \ Q(p)$.
\end{proof}
If $n$ is a tau number, then $\tau(n)$ has a similar as possible a factorization to
$n$
in some sense. Tau numbers maximize $\gcd(n,\tau(n))$. This motivates the
following definition:
\bigskip
\noindent{\bf Definition.} The positive integer $n$ is said to be an {\it anti-tau
number} if $\gcd(n, \tau(n))=1$.
Note an integer $n$ is a tau number iff $\lcm(n, \tau(n))=n$.
Thus in some sense, an integer
$n$ is a tau number if
$\lcm(n, \tau(n))$ is minimized. Now, if $\gcd(n, \tau(n)) = 1$ then
$\lcm(n,
\tau(n))= n \tau(n)$. Thus the anti-tau numbers
represent the numbers that maximize
$\lcm(n, \tau(n))$.
Note that if two tau numbers are relatively prime then their product is a
tau number. But as
the pairs (3,4), (3,5) and (13,4) demonstrate, the product of two
relatively
prime anti-tau numbers can be a tau number, an anti-tau number, or
neither.
The following Theorem summarizes the basic properties of anti-tau numbers.
\begin{theorem}
\begin{itemize}
\item[(a)] The only tau number that is also an anti-tau number is $1$.
\item[(b)] If $a$ is an even anti-tau number, then $a$ is a perfect
square.
\item[(c)] For $a,b>1$, $\gcd(a,b)=1$ $a$ is a tau number
and $b$ is an anti-tau number then $ab$ is
neither a tau nor an anti-tau number.
\item[(d)] Any odd square-free number is an anti-tau number.
\item[(e)] For any constant integer $C$, where primes $a_1,a_2\dots a_k$
are all
less
than $C$ and then for some primes distinct $p_1,p_2,\dots...p_k$ all
greater
than $C$, then for any positive integers, $b_1,b_2 \dots b_k$ the number
$(a_1^{{p_1^{b_1}}-1})(a_2^{{p_2^{b_2}}-1})\cdots(a_k^{{p_k^{b_k}}-1})$ is
an
anti-tau number.
\end{itemize}
\label{thm22}
\end{theorem}
Part (b) of the above theorem shows
that the anti-tau numbers are unlike the tau numbers
in more than one way,
since a corresponding rule exists about the odd tau numbers.
Part (c) can be considered a cancellation law of sorts. Parts (d) and (e)
motivates the following conjecture. Let $AT(n)$ denote the number
of numbers $\leq n$ that are anti-tau numbers.
\begin{conjecture}
%Conjecture 11:
For all $n>3$, the inequality $T(n) < AT(n)$ holds.
\label{conj11}
\end{conjecture}
The following results indicate the above conjecture is true for all
sufficiently large $n$.
\begin{theorem}
The density of the anti-tau numbers is at least $3/ \pi^2$.
\label{thm23}
\end{theorem}
\begin{proof}
This follows immediately from Theorem~\ref{thm22} (d) and the
fact that the
square free numbers have density
$6/\pi^2$.
\end{proof}
\begin{theorem}
For all sufficiently large $n$, $T(n) < AT(n)$. In fact $\lim_{n
\rightarrow
\infty} T(n)/AT(n) =0$.
\label{thm24}
\end{theorem}
\begin{proof}
This theorem follows immediately
from the density of the anti-tau numbers together
with Kennedy and Cooper's result that the tau numbers have zero density.
\end{proof}
Conjecture~\ref{conj11} is intuitive. In order for $n$ to be not tau, all
$\tau(n)$ needs is to have too high a prime power in its factorization or
a
prime that is not a factor of $n$. However, in order for $n$ not to be
anti-tau, $\tau(n)$ needs a prime factor of $n$, a much stronger
condition.
Colton also conjectured the non-existence of
three consecutive tau numbers. We shall
prove the slightly stronger result that if $a$ is an odd integer such
that
$a, a+1$ are both tau numbers then $a=1$.
A few remarks:
Colton started by assuming that he had three tau numbers $a-1,a,a+1$
and then showed using the basic congurence restrictions on the tau numbers
that
$a$ was
an odd perfect square and $a+1$ was twice an odd perfect square. However,
it
is easy to see that this restriction applies equally well if we substitute
the assumption that $a-1$ is a tau number for assuming $a$ is odd. Colton
then
examined the resulting Diophantine equation $x^2 +1 = 2y^2$ and was able
to
produce other restriction on the necessary properties of the triple based
on
this well-known equation.
\begin{theorem}
If $a$ is an odd integer such that $a, a+1$ are tau numbers then $a=1$.
\label{thm25}
\end{theorem}
\begin{proof}
By the above comments, we really need to look at the Diophantine equation
$x^2+1=2y^2$. Now it is a well known result that any odd divisor of
$x^2+1$
must be congruent to $1$ (mod 4) \cite{Shirali}. So every odd divisor of
$2y^2$ must be congruent to $1$ (mod 4). But $2y^2$ is a tau
number, so every odd prime
in its factorization must be raised to an exponent divisible by $4$ since
otherwise $2y^2$ would be divisible some number of the form $3$ mod 4.
Thus
$2y^2 = 2w^4$ for some $w$. So we really need to solve $x^2+1=2w^4$. This
is a Diophantine equation which has only the
solutions $(x,w) =(1,1)$ and
$(x,w)=(239,13)$ \cite{Steiner}.
The second solution fails to yield a tau number and
so $x=1$.
\end{proof}
The known proofs that these are the only positive solutions of this
final
Diophantine equation are quite lengthy and involved. It would be
interesting to find a way of proving the desired result without relying on
the equation, or possibly, a simple proof that (1,1) is the only tau
solution of the equation.
\section{Acknowledgments}
The author would like to thank the referee for useful comments.
The author would also like thank Jeffrey Shallit, Stephen David Miller,
Simon Colton,
David Speyer, Glenn Stevens, Aaron and Nathaniel Zelinsky, Aaron Margolis,
Mogs Wright, David McCord, Kevin Hart and the rest of the ever supportive
math department of the Hopkins School in New Haven, Connecticut.
\begin{thebibliography}{1}
\bibitem{Colton}
Simon Colton, Refactorable numbers --- a machine invention,
{\it Journal of Integer Sequences} {\bf 2}, Article 99.1.2,
{\tt http://www.math.uwaterloo.ca/JIS/colton/joisol.html}.
\bibitem{Hardy}
G. H. Hardy and E. M. Wright, {\it An Introduction to the Theory
of Numbers}, Oxford University Press, 1985.
\bibitem{Kennedy} R. E. Kennedy and C. N. Cooper, Tau numbers, natural
density, and Hardy and Wright's Theorem 437, {\it Internat.\
J. Math.\ Math.\ Sci.} {\bf 13} (1990), 383--386.
\bibitem{Ribenboim} Paulo Ribenboim, Catalan's Conjecture, {\it
Amer.\ Math.\ Monthly} {\bf 103} (1996), 529--538.
\bibitem{Shirali} Shailesh A. Shirali, A family portrait of the primes
--- a
case study in discrimination, {\it Math.\ Mag.} {\bf 70} (1997),
263--272 .
\bibitem{Dusart} P. Dusart, The $k$th prime is greater than $k(\ln
k+\ln\ln
k-1)$ for $k> 2$,
{\it Math. Comp.} {\bf 68} (1999), 411--415.
\bibitem{Steiner} Ray Steiner and Nikos Tzanakis, Simplifying the
solution of Ljunggren's equation $x^2 +1 = 2y^4$, {\it
J. Number Theory} {\bf 37} (1991) 123--132.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2000 {\it Mathematics Subject Classification}: Primary 11B05; Secondary 11A25.\ \
\noindent \emph{Keywords: tau number, number-of-divisors function}
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequence \seqnum{A033950}.)
\vspace*{+.1in}
\noindent
Received August 1, 2002;
revised version received December 15, 2002.
Published in {\it Journal of Integer Sequences} December 16, 2002.
Corrections, February 17, 2003.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.
\end{document}
*