Kvant Math Problem 785

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 9m37s
Source on kvant.digital

Problem

1. For an increasing sequence of positive numbers $a(n)$, $n=1$, 2, 3, $\ldots$, it is known that for every natural number $k>1$ there exists a number $b_k$ such that $$a(kn) \le b_k, a(n)$$ for all $n$. Prove that there exist positive numbers $c$ and $\alpha$ for which $$a(n) \le c n^{\alpha} \quad \text{при всех}~n \ge1.$$

Is this statement still true if in the condition

1. the word “any” is replaced by “some”?
2. we do not require the sequence $a(n)$ to be increasing?

M. U. Gafurov

Exploration

The hypothesis states that for every integer $k>1$ there exists a constant $b_k$ such that

$$a(kn)\le b_k,a(n)\quad \text{for all }n\in\mathbb{N},$$

with $a(n)$ increasing and positive.

The inequality controls how much the sequence can grow under dilation by any fixed factor. In particular, choosing $k=2$ gives a uniform doubling bound

$$a(2n)\le b_2 a(n),$$

which already suggests iterating along powers of $2$:

$$a(2^m)\le b_2^m a(1).$$

This yields exponential growth in $m$, hence polynomial growth in $n=2^m$.

The difficulty is extending this from powers of $2$ to arbitrary $n$, and ensuring that no hidden oscillations occur between dyadic points. The monotonicity assumption allows comparison between $a(n)$ and nearby powers of $2$.

For the variants, if “for every $k>1$” is replaced by “for some $k>1$”, the same dyadic-type argument should still work using that specific $k$.

If monotonicity is removed, the key obstruction is that control at multiples does not prevent isolated spikes between controlled points.

Problem Understanding

This is a Type B problem: prove that a sequence satisfying multiplicative boundedness grows at most polynomially.

We are given a scaling inequality for every dilation factor, and must deduce a global power bound:

$$a(n)\le c n^\alpha.$$

The core idea is that repeated scaling by a fixed integer (such as $2$) forces exponential control in the logarithmic scale, which becomes polynomial in $n$.

The answer is that such $c$ and $\alpha$ do exist under the stated conditions, and the mechanism is iteration of the inequality at a fixed scale.

Proof Architecture

First, we prove that choosing $k=2$ yields a uniform doubling inequality with constant $B=b_2$.

Second, we prove by induction that

$$a(2^m)\le B^m a(1)$$

for all $m\ge 0$.

Third, we convert this into a polynomial bound on powers of $2$ by writing $B^m = 2^{m\log_2 B}$.

Fourth, we extend the bound from powers of $2$ to arbitrary $n$ using monotonicity of $a(n)$ and comparison with the next power of $2$.

The most delicate point is the passage from dyadic points to all integers; without monotonicity, this step fails.

Solution

We begin by selecting $k=2$ in the hypothesis. Then there exists a constant $b_2>0$ such that

$$a(2n)\le b_2 a(n)\quad \text{for all }n\ge 1.$$

Denote $B=b_2$.

We prove by induction on $m$ that

$$a(2^m)\le B^m a(1).$$

For $m=0$ this is equality. Assume the statement holds for some $m$. Then applying the inequality with $n=2^m$ gives

$$a(2^{m+1})=a(2\cdot 2^m)\le B a(2^m)\le B\cdot B^m a(1)=B^{m+1}a(1),$$

which completes the induction.

Let $n$ be arbitrary. Choose $m$ such that

$$2^m\le n<2^{m+1}.$$

Since $a(n)$ is increasing,

$$a(n)\le a(2^{m+1}).$$

Using the dyadic bound,

$$a(2^{m+1})\le B^{m+1}a(1).$$

Hence

$$a(n)\le a(1),B^{m+1}.$$

We now express this in terms of $n$. From $n\ge 2^m$ we obtain $m\le \log_2 n$. Thus

$$B^{m+1}\le B\cdot B^{\log_2 n}=B\cdot n^{\log_2 B}.$$

Therefore

$$a(n)\le a(1)B, n^{\log_2 B}.$$

Setting $c=a(1)B$ and $\alpha=\log_2 B$ yields

$$a(n)\le c n^\alpha\quad \text{for all }n\ge 1.$$

This completes the proof.

∎

We now address the variants.

If “for every $k>1$” is replaced by “for some $k>1$”, then the same argument applies with that fixed $k_0>1$ in place of $2$. Writing

$$a(k_0 n)\le b_{k_0} a(n)$$

and iterating gives

$$a(k_0^m)\le b_{k_0}^m a(1),$$

which again yields a polynomial bound with exponent $\log_{k_0} b_{k_0}$, and monotonicity extends the bound to all $n$ exactly as before.

If monotonicity is removed, the conclusion fails. The multiplicative inequality only controls values at multiples, allowing construction of sequences that are extremely small at most points but take very large values at specially chosen integers, while still satisfying

$$a(kn)\le b_k a(n)$$

because the constraint propagates only forward along multiplicative chains. Without monotonicity, there is no mechanism forcing intermediate values to be comparable with dyadic points, and the extension step used above breaks down.

Verification of Key Steps

The induction for $a(2^m)$ depends only on repeated application of the given inequality at $n=2^m$, so no hidden assumption is used.

The conversion $B^m = 2^{m\log_2 B}$ is exact by the definition of logarithms.

The critical step is bounding $a(n)$ by $a(2^{m+1})$, which uses monotonicity in an essential way; without it, no inequality between $a(n)$ and nearby dyadic points is available.

The passage from $m+1\le \log_2 n+1$ to a power bound is exact and preserves uniform constants independent of $n$.

Alternative Approaches

One alternative approach works in logarithmic variables by setting $f(n)=\log a(n)$ and studying the inequality

$$f(2n)\le f(n)+C,$$

which leads to subadditivity along dyadic scales. Iteration produces linear growth in $\log n$, hence polynomial growth in $n$.

Another approach uses repeated factorization of $n$ into powers of $k_0$ and a remainder, avoiding monotonicity if one works only on the subsequence $k_0^m$ and then extends carefully. The present method is preferable because it isolates a single scaling factor and reduces the argument to a clean induction.