| It's strange how much the previous two responses furthered my investigation.
While trying to write an explanation for what I was doing, everything fell into
place. A description of an uncountable number of functions that meet the
problem's specifications follows, along with a proof. NOTES is not the best
way to convey mathematical formulae or explanations, so feel free to ask for
more explanations, either electronically or in person.
First, let me explain some notation. f[a]^b(c) is function f subscript a,
composed with itself b times (with zero times representing identity and
negative one times representing the inverse of f[a], which will be 1-1 when the
inverse is used) evaluated at c. Occasionally, I will also use the fact that
functions are sets of ordered pairs, so I will do something such as take the
union of functions. And { a | there exists a b such that (a,b) is in f } =
dom(f) and { b | there exists an a such that (a,b) is in f } = ran(f). The
domain of f and the range of f should be understood to be identical to dom(f)
and ran(f). But when I say f is a function from X to Y, X is not necessarily
dom(f), and Y is not necessarily ran(f); they may have other, unused elements.
For convenience, I will use A to be the half-open interval (0,pi/6], B to be
(pi/6,1], and C to be the union of A and B. Also, p(x) = sin 3x, and q(x) =
p^-1(x) = (1/3) asin x, where asin = sin^-1. We also define p's domain to be
restricted to A and q's domain to be restricted to C. Observe that this makes
the range of p C and the range of q A.
Next, we need a few lemmas.
Lemma 0.0. p is 1-1. Recall that p is restricted to A. Over this domain,
its derivative, 3 cos 3x, is positive except at a single point.
Hence p is strictly monotonic, so it must be 1-1. (This also
means p's inverse, q, exists.)
Lemma 0.1. q is 1-1, since it is the inverse of a function, p.
Lemma 0.2. When q's domain is restricted to A, q(x) < x. This is
equivalent to saying x-q(x) > 0. Observe that x - ((1/3)
asin x) = 0 at x = 0. Its derivative, 1 - 1/(3sqrt(1-x^2)),
is positive at every point in A, so x - ((1/3) asin x) is
strictly increasing over [0,pi/6] and must be positive at
every point in A.
Let g[0] be any 1-1 function from B to B such that x is in B implies (x is in
dom(g[0]) iff x is not in ran(g[0])). Clearly, such functions exist.
For integers i, i > 0, let g[i] be a function from C to C such that g[i](x) =
q(g[i-1]^-1(x)) for each x in the range of g[i-1]. Observe that g[i-1] is a
function, so its inverse (which exists since g[i-1] is 1-1) is 1-1. Also, the
range of g[i-1]^-1 is some subset of C, so it is also a subset of the domain of
q. Hence the composition (q composed with g[i-1]^-1) is properly formed. And
since both functions are 1-1, the resulting function, g[i], is 1-1. And its
range is some subset of the range of q, A, which is a subset of C.
Lemma 1.0. dom(g[1]) = ran(g[0]), so the union of dom(g[1]) and dom(g[0])
equals the union of ran(g[0]) and dom(g[0]) which equals B.
Now let g[P] be the union, for all non-negative integers i, of g[i]. Now we
need to show that g[P] is a function. This can be accomplished by showing
that the domains of all the g[i] are disjoint, so any value in the domain of
g[P] can only be mapped to a value through one g[i]. Showing the domains
are disjoint will also show the ranges are disjoint (since the range of each
g[i] is the domain of g[i+1]). Since each g[i] is 1-1, this will also mean
g[P] is 1-1.
Lemma 1.1. B is a subset of dom(g[P]). This follows from Lemma 1.0 and
the definition of g[P].
To prove the domains of all the g[i] are disjoint, suppose they are not. Then
there exist non-equal integers i and j and a number in C, x, such that x is in
dom(g[i]) and x is in dom(g[j]). Without loss of generality, suppose i < j,
and that i is the least such i for which these things are true. Clearly, j >
0, so, by definition of g[j], x is in the range of g[j-1].
Case 0. i <= 1.
Case 0.0. j = 1.
Since x is in ran(g[j-1]), x is in ran(g[0]). But i must be
0, so x is in dom(g[0]). But by definition of g[0], x is in
dom(g[0]) iff x is not in ran(g[0]), so this is a
contradiction.
Case 0.1. j > 1.
Since x is in ran(g[j-1]) and j-1 > 0, there exists a w such
that x = q(g[j-2]^-1(w)), by definition of g[j-1]. Thus, x is
in the range of q. And we know the range of q is A. But
x is in dom(g[0]) or dom(g[1]), depending on whether i is
0 or 1. By Lemma 1.0, x is in B. But A and B are clearly
disjoint, so this is a contradiction.
Case 1. i > 1.
Again, there exists a w such that x = q(g[j-2]^-1(w)). And since
i-1 > 0, there exists a v such that x = q(g[i-2]^-1(v)). But q is
1-1, so g[j-2]^-1(w) = g[i-2]^-1(v). Let u = g[j-2]^-1(w). We see
that u is in the ranges of g[j-2]^-1 and g[i-2]^-1, so u is in the
domains of g[j-2] and g[i-2]. Thus, i-2 and j-2 are non-equal
integers with i-2 < j-2 such that u is a number in the domains of
both g[j-2] and g[i-2]. This contradicts the supposition that i
is the least such number, since i-2 < i.
Therefore the supposition that the domains of all the g[i] are not disjoint
is false. g[P] is a 1-1 function.
Lemma 1.2. For any integer i, g[i](x) = y implies g[P](x) = y. This
follows from the definition of a function and the definition
of g[P].
Let f[P] = g[P]^-1. Since g[P] is a 1-1 function, f[P] is a 1-1 function. Let
f[Z] be the identity function restricted to { 0 }, that is, f[Z](0) = 0. Let
f[N] be a function from [-1,0) to [-1,0) such that f[N](x) = -f[P](-x). Let
f[U] = the union of f[P], f[Z], and f[N]. Let f be a function from the reals
to the reals such that f(x) = f[U]( (1/3) asin (sin 3x) ). f is a function
requested by the problem.
Proof:
We need to prove two things, that every real number x is in the domain of f
and that, if x is in the domain of f, f(f(x)) = sin 3x.
Suppose x is some number in (0,pi/6] (that is, A) and dom(f[P]). f[P] =
g[P]^-1, so x is in dom(g[P]^-1), so x is in ran(g[P]). By definition of g[P],
there must be an integer i such that x is in ran(g[i]). Since ran(g[0]) is a
subset of B, and x is in A, i is not 0. So, by definition of g[i], there must
exist a w such that x = g[i](w) = q(g[i-1]^-1(w)). Thus, p(x) = g[i-1]^-1(w).
Also, w = g[i]^-1(x), so p(x) = g[i-1]^-1(g[i]^-1(x)). Thus g[i](g[i-1](p(x)))
= x. By Lemma 1.2, g[P](g[P](p(x))) = x. And p(x) = g[P]^-1(g[P]^-1(x)).
Replacing sin 3x for p(x) and f[P] for g[P]^-1, we have sin 3x = f[P](f[P](x)),
for x in (0,pi/6]. Over this restricted domain, f = f[P], so sin 3x = f(f(x))
in this domain. Clearly, f(f(0)) = f(0) = 0 = sin 3*0. And for the domain
[-pi/6,0), f(f(x)) = -f(--f(-x)) = -f(f(-x)) = - sin 3(-x) = sin 3x. If x is a
number outside of [-pi/6,pi/6], f(f(x)) = f(f[U](1/3 asin (sin 3x))). Let u =
1/3 asin (sin 3x). Clearly, sin 3x = sin 3u. And u is in [-pi/6,pi/6], so
f(f(x)) = f(f[U](u)) = f(f(u)) = sin 3u. So for every x in the domain of f,
f(f(x)) = sin 3x.
Over the restricted domain [-pi/6,pi/6], f = f[U]. 0 is obviously in the
domain of f[U], and hence f. Also, if every number in (0,pi/6] is in
dom(f[P]), every number in [-pi/6,0) is clearly in dom(f[N]), so every number
in [-pi/6,pi/6] is in dom(f). And since every real number is in the domain
of 1/3 asin (sin 3x) and the range of this function is [-pi/6,pi/6], every
real number will be in dom(f). All that remains is to show that every x in
(0,pi/6] is in dom(f[P]).
Consider an x in (0,pi/6]. Suppose x is not in dom(f[P]). Then x is not
in ran(g[P]), so there does not exist an integer i such that x is in ran(g[i]).
Consider p(x). By Lemma 0.2, q(p(x)) < p(x), so x < p(x). Consider the
sequence p^m(x), for non-negative integers m.
There must be an integer n such that p^n(x) is in B. To see this, suppose
there is no such integer. The range of p is C, so if, for any m, p^m(x) is not
in B, it must be in A. Observe that p^1(x) >= x + 1*(p(x)-x) and p(x)-x is
positive. Also, p^0(x) = x >= x + 0*(p(x)-x). Suppose that p^i(x) >= x +
i*(p(x)-x) for all i < j and j > 1. Now q(p^j(x)) < p^j(x), by Lemma 0.2, so
p^(j-1)(x) < p^j(x). Clearly, p^j(x) > p(x) (since p^j(x) > p^(j-1)(x) >
p^(j-2)(x) . . .). Since x-q(x) is strictly increasing, as mentioned in Lemma
0.2, then p^j(x)-q(p^j(x)) > p(x)-q(p(x)), so p^j(x) > p^(j-1)(x)+p(x)-x.
p^(j-1)(x) >= x + (j-1)*(p(x)-x), by supposition, so p^j(x) >= x + (j-1)*
(p*x)-x) + p(x)-x, so p^j(x) >= x + j*(p(x)-x). By induction, this is true
for all integers j.
Now let n be an integer greater than (1-x)/(p(x)-x). Then p^n(x) > x +
(1-x)/(p(x)-x)*(p(x)-x), so p^n(x) > x + (1-x) = 1. But the range of p is
C, so p^n(x) cannot be greater than one. This is a contradiction, so, the
supposition that there is no integer n such that p^n(x) is in B is false.
Now let n be the least integer such that p^n(x) is in B or p^n(x) is in the
domain of some g[i]. We know there must be such an n. Also, if p^n(x) is
in B, then it must be in dom(g[0]) or dom(g[1]), so p^n(x) is in dom(g[i]),
for some integer i. We know n is not zero, since x is not in the domain
of any g[i]. Since n is the least such n, p^(n-1)(x) is not in the domain
of any g[i]. But consider g[i+1](g[i](p^n(x))). This exists since p^n(x)
is in dom(g[i]), so g[i](p^n(x)) is in ran(g[i]), so it is in dom(g[i+1]),
by definition of g[i+1]. But g[i+1](g[i](p^n(x))) = q(g[i]^-1(g[i](p^n(x)))),
by definition of g[i+1], and this equals q(p^n(x)) = p^(n-1)(x), so p^(n-1)(x)
is in ran(g[i+1]), so it is in dom(g[i+2]), which contradicts the statement
that p^(n-1)(x) is not in the domain of any g[i].
So the supposition that there is an x in (0,pi/6] is false, and this completes
the proof.
-- edp
|
| Some of you have seen this response before; I noticed a typographical error
in a couple of the formulas and wanted to correct it.
================================================================================
Note 398.15 Bjorn Poonen Problems 15 of 15
BEING::POSTPISCHIL 105 lines 30-DEC-1985 12:35
--------------------------------------------------------------------------------
Here is a proof for the second problem.
Let n be a positive integer. Let P be the greatest prime not greater than n.
All other variables are restricted to the positive integers unless otherwise
indicated. [[x]] denotes the greatest integer not greater than x.
Let f[n,P](m) = m/[(m-1)(P-1)] - n/[(n-1)(P-1)]. If m > n, then f[n,P](m) is
positive. In fact, f[n,P] is strictly increasing for positive integers, so if
m > n, f[n,P](m) >= f[n,P](n+1).
Consider (1/(m-1))[(ln m/ln P)+2]. For a given P, this expression can be made
as small as is desired by increasing m, because its limit as m goes to
infinity, using l'Hospital's rule, is the same as the limit of 1/[m (ln P)],
which is zero.
By the definition of limit, for each positive real number, e, there is a
positive number d such that (1/(m-1))[(ln m/ln P)+2] is less than e when m > d.
Let M be the greater of n+1 or the value of this d when e is f[n,P](n+1). Then
f[n,P](n+1) - (1/(m-1))[(ln m/ln P)+2] is positive when m > M. Since f[n,P](m)
>= f[n,P](n+1), f[n,P](m) - (1/(m-1))[(ln m/ln P)+2] is positive when m > M.
If f[n,P](m) - (1/(m-1))[(ln m/ln P)+2] is positive, then f[n,p](m) -
(1/(m-1))[(ln m/ln p)+2] is positive for p <= P (because the derivative of that
expression with respect to p is negative for positive p, so it is strictly
decreasing).
infinity
Consider (1/(m-1)) sum (m mod p^i)/p^i, also written (1/(m-1)) sum[i=1,infinity]
i=1
(m mod p^i)/p^i, where p is some prime number. For positive m, this expression
is positive. What is its maximum value? The worst case is no worse than (m
mod p^i) being p^i-1 for some number of i's until p^i > m, followed by a
geometric series, m/p^i. If j is the index of the second term for which p^j >=
m, then the geometric series from that point on has the sum (m/p^j)/(1-1/p) =
m/((p^(j-1))(p-1)) <= m/p^(j-1). Since j is the index of the second term for
which p^j >= m, p^(j-1) >= m, so m/p^(j-1) <= p^(j-1)/p^(j-1) = 1, so the sum
of the geometric series beginning at j is less than or equal to 1. Now the
number of terms before the geometric series is j-1. And each of these j-1
terms is less than one (since they are at most (p^i-1)/p^i. So the sum of the
series is less than j-1 ones plus one for the geometric series, so
sum[i=1,infinity] (m mod p^i)/p^i < j. Now j is the second term for which p^j
>= m, so p^(j-2) < m. This means that the logarithm with base p of m is
greater than j-2, so j < (ln m)/(ln p) + 2. So the sum is less than (ln m)/(ln
p) + 2, and the entire expression is less than (1/(m-1))[(ln m)/(ln p)+2].
Since that expression is less than (1/(m-1))[(ln m/ln p)+2], f[n,p](m) -
(1/(m-1)) sum[i=1,infinity] (m mod p^i)/p^i is greater than f[n,p](m) -
(1/(m-1))[(ln m/ln p)+2]. Since the latter is greater than zero, the former
is greater than zero. Expanding f, we have:
m/[(m-1)(p-1)] - n/[(n-1)(p-1)] -
(1/(m-1))sum[i=1,infinity](m mod p^i)/p^i > 0.
Now, (1/(n-1))sum[i=1,infinity](n mod p^i)/p^i is positive, so
m/[(m-1)(p-1)] - n/[(n-1)(p-1)] -
(1/(m-1))sum[i=1,infinity](m mod p^i)/p^i +
(1/(n-1))sum[i=1,infinity](n mod p^i)/p^i > 0.
This leads to
m/[(m-1)(p-1)] - (1/(m-1))sum[i=1,infinity](m mod p^i)/p^i >
n/[(n-1)(p-1)] - (1/(n-1))sum[i=1,infinity](n mod p^i)/p^i.
Observe that m/[(m-1)(p-1)] = (1/(m-1))[m/(p-1)] = (1/(m-1))[m/(p(1-1/p))] =
(1/(m-1)) sum[i=1,infinity](m/p^i). Substituting this above, along with the
corresponding substitution for n, gives
(1/(m-1))sum[i=1,infinity](m - m mod p^i)/p^i >
(1/(n-1))sum[i=1,infinity](n - n mod p^i)/p^i.
Multiply both sides by (m-1)(n-1) gives
(n-1) sum[i=1,infinity](m - m mod p^i)/p^i >
(m-1) sum[i=1,infinity](n - n mod p^i)/p^i.
Observe that [[a/b]] = (a - a mod b)/b, so the above statement is
(n-1) sum[i=1,infinity] [[m/p^i]] > (m-1) sum[i=1,infinity] [[n/p^i]].
Recall that this holds for all m > M and p <= P. Now, there is obviously no
prime number greater than P which factors n!, since P is the greatest prime
not greater than n. This also means there is no prime greater than P which
factors n!^(m-1), since that would mean it factors n!.
Suppose, for some m > M, m!^(n-1)/n!^(m-1) is not an integer. Then there must
be some prime, q, which factors n!^(m-1) more times than it factors m!^(n-1).
But for any prime, q, the number of times it factors x! is
sum[i=1,infinity] [[x/q^i]]. This is because the first term of the series
counts the number of numbers in x(x-1)(x-2)...1 which have q as a factor at
least once; the second term counts the number of numbers which have q as a
factor as least twice (which are counted once in the first term and once in
the second term); and so on. And the number of times q factors x!^y is
obviously just that sum multiplied by y. So if q factors n!^(m-1) more times
than it factors m!^(n-1), then q <= P and
(n-1) sum[i=1,infinity] [[m/q^i]] < (m-1) sum[i=1,infinity] [[n/q^i]],
but this is a contradiction. Therefore, the supposition that there is an m
> M such that m!^(n-1)/n!^(m-1) is not an integer is false, so it is an integer
for all m > M, of which there are infinitely many.
-- edp
|