So in my standard math curriculum for logarithmic functions, we have to plot like 9+ points, and it got me wondering if all of those points are even needed. How many points does a logarithmic function even need to be uniquely determined?
So at first I thought of a model,
y = a log F(x) + c
Where,
- a and c are constants
- F(x) is a polynomial of x (E.g., ax+c, ax^2+bx+c, etc.)
If we let m be the total number of points needed, my proof says m needs to be at least,
m >= 2d+1+⌊d/2⌋
Where, d is the degree of F(x).
TL;DR: The proof below is very long.
Setting it up
Let d ≥ 1. F, G real polynomials of degree at most d, a and ã nonzero real constants. Take distinct real numbers
x₁ < x₂ < ⋯ < x_m
with F(xᵢ) > 0 and G(xᵢ) > 0 for every i. Suppose
y = a log F(x) + c and y = ã log G(x) + c̃
agree at every xᵢ. Then if m ≥ 2d + 1 + ⌊d/2⌋, the two models are identical on every interval where both logs are defined. Agreement at enough points forces the same curve.
Transforming the problem
At each sample point,
a log F(xᵢ) + c = ã log G(xᵢ) + c̃.
Divide by a ≠ 0 and set α = ã/a, β = (c̃ − c)/a. Since a, ã ≠ 0, we get α ≠ 0. The equality becomes
log F(xᵢ) − α log G(xᵢ) − β = 0.
So define
H(x) = log F(x) − α log G(x) − β,
and H(xᵢ) = 0 for every i. Differentiating,
H′(x) = F′(x)/F(x) − α G′(x)/G(x) = [F′(x)G(x) − α G′(x)F(x)] / [F(x)G(x)].
Let
Q(x) = F′(x)G(x) − α G′(x)F(x).
Since deg F, deg G ≤ d, we have deg(F′G) ≤ 2d−1 and deg(G′F) ≤ 2d−1, so
deg Q ≤ 2d−1
Now, we must show Q has at least 2d distinct real zeros, which can force Q≡0.
Counting roots inside sample intervals
Lemma: if a real polynomial P is positive at both endpoints of an interval (u,v), then the sum of the multiplicities of its real roots inside (u,v) is even.
Why? At a real root r of multiplicity k, write P(x) = (x−r)^k S(x) with S(r) ≠ 0. The sign of P changes across r iff k is odd. Positive at both endpoints means an even number of sign changes, so the total multiplicity is even.
Corollary: Let P be a real polynomial of degree at most d with P(xᵢ) > 0 for all i. Then P has a real root in at most ⌊d/2⌋ of the intervals Iᵢ = (xᵢ, x_{i+1}).
Why? By the lemma, any interval containing a root of P contains real roots whose multiplicities sum to at least 2. These intervals are disjoint, so the total multiplicity in their union is at least twice the number of such intervals. That total is at most deg P ≤ d. So the number of such intervals is at most ⌊d/2⌋.
Apply this to F and to G separately. Set
A = {Iᵢ : F has a root in Iᵢ}, B = {Iᵢ : G has a root in Iᵢ}.
Then |A| ≤ ⌊d/2⌋ and |B| ≤ ⌊d/2⌋, so in particular |A ∩ B| ≤ ⌊d/2⌋
Getting zeros of Q from the intervals
Call an interval clean if neither F nor G has a root in it, exclusive if exactly one does, shared if both do.
Clean intervals. F and G are positive at both endpoints and have no roots inside, so by continuity F > 0 and G > 0 on [xᵢ, x_{i+1}]. So H is continuous on the closed interval and differentiable on the open one. Since H(xᵢ) = H(x_{i+1}) = 0, Rolle gives r ∈ (xᵢ, x_{i+1}) with H′(r) = 0. But H′(r) = Q(r)/(F(r)G(r)), and F(r)G(r) ≠ 0, so Q(r) = 0.
Exclusive intervals. Say Iᵢ contains roots of F but none of G (the other case is symmetric). G > 0 on [xᵢ, x_{i+1}]. Two possibilities:
If F has a multiple root r in Iᵢ, then F(r) = F′(r) = 0, so Q(r) = F′(r)G(r) − α G′(r)F(r) = 0.
If every root of F in Iᵢ is simple, the lemma says there's an even number of them: r₁ < r₂ < ⋯ < r_{2k}. Between consecutive roots, F has constant sign. Since both are simple, the sign just right of rⱼ is sgn F′(rⱼ), and the sign just left of r_{j+1} is −sgn F′(r_{j+1}). These agree, so sgn F′(rⱼ) = −sgn F′(r_{j+1}). At each root, Q(rⱼ) = F′(rⱼ)G(rⱼ), and G(rⱼ) > 0, so Q(r₁) and Q(r₂) have opposite signs. By IVT, Q has a zero in (r₁, r₂) ⊂ Iᵢ.
Either way, Iᵢ contributes at least one zero of Q. The symmetric argument (Q(s) = −α G′(s)F(s) at a root s of G, with F(s) > 0 and α ≠ 0) handles the case where G has roots, and F doesn't.
So every clean or exclusive interval contains at least one zero of Q.
Shared intervals. If both F and G have roots in Iᵢ, we just throw Iᵢ away. That costs us at most |A ∩ B| intervals.
Counting the zeros
Usable intervals: (m−1) − |A ∩ B| ≥ m − 1 − ⌊d/2⌋. Each gives at least one zero of Q, and zeros from distinct intervals are distinct since the intervals are disjoint. So Q has at least
m − 1 − ⌊d/2⌋
distinct real zeros. By hypothesis m ≥ 2d + 1 + ⌊d/2⌋, so
m − 1 − ⌊d/2⌋ ≥ 2d.
So Q has at least 2d distinct real zeros. But deg Q ≤ 2d−1, so Q can't be nonzero. Therefore Q ≡ 0.
From Q ≡ 0 to identical models
We have
F′G − α G′F ≡ 0. (1)
Since F(xᵢ) > 0 and G(xᵢ) > 0 at the sample points, neither F nor G is the zero polynomial.
If F is constant, then F′ ≡ 0, so (1) gives α G′F ≡ 0. Since α ≠ 0 and F ≢ 0, G′ ≡ 0, so G is constant. Then both models are constant, and since they agree at a sample point, they're the same constant. Same if G is constant. So assume both are nonconstant.
Divide (1) by FG (not identically zero):
F′(x)/F(x) = α G′(x)/G(x). (2)
Now work over ℂ. Let z be a root of F of multiplicity r ≥ 1. Near z,
F(x) = (x−z)^r U(x), U(z) ≠ 0, so F′/F = r/(x−z) + U′/U,
so F′/F has a simple pole at z with residue r. By (2), α G′/G has a pole at z, so z is a root of G. If its multiplicity in G is s, then α G′/G has residue αs at z, so
r = αs. (3)
Reversing roles, every root of G is a root of F. So F and G have the same distinct complex roots.
Since F is nonconstant, at least one such root z exists. From (3), α = r/s (Uh, it is supposed to be a fraction; I don't know why Reddit is thinking it's some subreddit), a ratio of positive integers — so α is rational and positive. Write α = p/q in lowest terms with p, q positive coprime. Then (3) reads qr = ps, and since gcd(p,q) = 1 there's a positive integer k_z with
r = p k_z, s = q k_z.
Let P be the monic real polynomial whose roots are the distinct complex roots of F (equivalently of G), each to multiplicity one. Since F is real, its nonreal roots come in conjugate pairs with equal multiplicity, so P is real. From the multiplicities, F and P^p have the same roots with the same multiplicities, and both are real, so
F = u P^p
for some nonzero real u. Similarly
G = v P^q
for some nonzero real v.
On any interval where F > 0 and G > 0, P(x) ≠ 0 and
log F(x) = log|u| + p log|P(x)|, log G(x) = log|v| + q log|P(x)|.
Therefore
log F(x) − α log G(x) = log|u| − (p/q) log|v|,
which is a constant C independent of x — and it's the same constant on every connected component of the common domain.
At each sample point xᵢ,
log F(xᵢ) − α log G(xᵢ) = β,
so C = β. Hence,
log F(x) − α log G(x) = β
on the entire common domain. Multiply by a and recall α = ã/a, β = (c̃ − c)/a:
a log F(x) − ã log G(x) = c̃ − c,
that is,
a log F(x) + c = ã log G(x) + c̃.
The two models are identical wherever both logs are defined.
Bounds table
And so on.
That also begs another question. Is this bound the optimal bound? Like, could you guarantee uniqueness for a cubic with fewer than 8 points? I don't have anything on that yet.