Uniqueness of $f( x y - 1) = f(x-1)f(y-1),f(1) = A,f(1+n)>f(n)$?

76 Views Asked by At

Let $ f(x)$ be defined for $x \ge 1$ Also it is analytic in $]1,\infty[$. For all integers $n>0$ : $ f(n+1) > f(n) $

$f(1) = A $ where $A$ is an integer $>1$.

$f(n)$ is always a positive integer. For $x-1,y-1 \ge 1 $ and $xy -1 \ge 3 $ we have

$$f(xy -1) = f(x-1)f(y-1)$$

For a given $A$ , how many solutions are there ? Does $A=3$ imply a Unique solution ? Does $A=2$ imply a Unique solution ?

Notice setting $x = y$ gives us an equation with a hyperbolic fixpoint so complex dynamics could be involved.

As for background the equation was given to me by tommy1729 and relates to the karatsuba algorithm. Notice the function f takes the degree of the polynomial and outputs an upper bound for the amount of products needed.

$$f(1) = 3 , f(2^n - 1) = 3^n$$

Is exactly karatsuba's result.

The upper bound raises the question if the number of multiplies is even less then the equation dictates or exact.

But that last question is too advanced for here i guess.

Just giving context and remarks.

The equation $f(x y - 1) = f(x -1)f(y-1) $ is called " Tommy - Karatsuba equation ".

I am unaware of another name for it. Inform me if so.

1

There are 1 best solutions below

1
On BEST ANSWER

Edit: If we're only interested at the value at positive integers, the condition that $f(xy - 1) = f(x - 1) f(y - 1)$ implies that the function $g : \mathbb{N} \to \mathbb{R}$ given by $g(1) = 1$ and $g(n) = f(n - 1)$ for $n \geq 2$ is completely multiplicative. Your condition that $f(n + 1) > f(n)$ tells us that it is increasing. Then see this question: A result of Erdős on increasing multiplicative functions


If you really do require $f$ to be defined for all real numbers in your interval and to be analytic, then the only possible solution for any value of $A$ are given by $f(x) = (x + 1)^\alpha$ for some real number $\alpha$, as I shall show below. For most values of $A$, this doesn't give you a function which is an integer at integer inputs, however. If you are only interested in functions from the natural numbers to the natural numbers which satisfy $f(xy - 1) = f(x - 1)f(y - 1)$, then there may be other solutions. I haven't thought about that case.

Weakening your assumptions slightly, we can show that the only functions $f : [1, \infty) \to \mathbb{R}$ which satisfy all of the following conditions:

  • $f(xy - 1) = f(x - 1) f(y - 1)$ for all $x, y \geq 2$
  • $f$ is continuous (not necessarily analytic) on $(1, \infty)$
  • $f(7) \neq 0$ (alternatively, we can assume that there are arbitrarily large values of $x$ for which $f(x) \neq 0$)

are given by $f(x) = (x + 1)^\alpha$ for some real number $\alpha$.

Let $I$ be the interval $(2\ln 2, \infty)$, and define the function $g : I \to \mathbb{R}$ by $g(x) = \ln(f(e^x - 1))$ for all $x \in I$.

To show that this does indeed define a function, we must show that $f(e^x - 1) > 0$ for all $x \in I$, or, equivalently, that $f(x) > 0$ for $x > 3$.

Now we know that for any $x \geq 2$ that we have $f(x^2 - 1) = f(x - 1)^2 \geq 0$, so $f(x) \geq 0$ for all $x \geq 3$.

Suppose that $f(x) = 0$ for some $x \geq 3$.

If we are assuming that there are arbitrarily large values of $x$ such that $f(x) \neq 0$, then this is already a contradiction, since if $z \geq 2x + 1$ is a value such that $f(z) \neq 0$, then we have that for $y = \frac{z + 1}{x + 1} \geq 2$ that $f(z) = f((x + 1)y - 1) = f(x)f(y - 1) = 0$.

Alternatively, if we are assuming that $f(7) \neq 0$, then we can argue as follows: If there is some $x \geq 4$ such that $f(x - 1) = 0$, then we also have that $f(\sqrt{x} - 1) = 0$. We can continue in this way, taking square-roots until we obtain that there is some $x \in [2, 4)$ such that $f(x - 1) = 0$. But then for $y = \frac{8}{x} > 2$, we have that $f(7) = f(xy - 1) = f(x - 1)f(y - 1) = 0$, a contradiction.

In any case, we have that $f(x) > 0$ for all $x \geq 3$, and so $g$ does indeed define a function from $I$ to $\mathbb{R}$. Now we note that on $I$, $g$ is a composition of continuous functions, and hence is continuous.

We also have that for any $x, y \in I$, that

$$ \begin{multline*} g(x + y) = \ln(f(e^{x + y} - 1)) = \ln(f(e^x e^y - 1)) = \ln(f(e^x - 1) f(e^y - 1) \\ = \ln(f(e^x - 1)) + \ln(f(e^y - 1)) = g(x) + g(y) \end{multline*} $$

It is then a standard result that this this together with the continuity of $g$ implies that $g(x) = \alpha x$ for all $x \in I$ for some constant $\alpha$.

We thus have that for all $x \in I$ that

$$ \alpha x = g(x) = \ln(f(e^x - 1)) $$

and so

$$ f(e^x - 1) = e^{\alpha x} $$

If $x \geq 3$, then we have that $\ln(x + 1) \in I$, and so

$$ f(x) = f\left(e^{\ln(x + 1)} - 1\right) = e^{\alpha \ln(x + 1) } = (x + 1)^\alpha $$

This only holds for $x \geq 3$, so we still need to show that it holds for $x \in [1, 3)$.

But for any $x \in [1, 3)$, we have that

$$ f(x) f(3) = f(4(x + 1) - 1) = f(4x + 3) $$

Since $3 \geq 3$ and $4x + 3 \geq 3$, this implies that

$$ f(x) \cdot 4^\alpha = (4x + 4)^\alpha = 4^\alpha (x + 1)^\alpha $$

from which it follows that

$$ f(x) = (x + 1)^\alpha $$.

This shows that indeed $ f(x) = (x + 1)^\alpha $ for all $x \in [1, \infty)$.

For a fixed value of $A = f(1)$, we see that if there is a solution then it is unique.

I think that for most values of $A$, there isn't a function that meets all of your requirements. You can see that the requirements you have for you function imply the conditions that I assumed $f$ satisfies. But $(x + 1)^\alpha$ is usually not an integer for integer $x$. For $A = 3$, for example, we would require $\alpha = \log_2{3}$, but then $f(2) = 3^{\log_2{3}}$ is not an integer.

For $A = 2$, the unique solution is $f(x) = x + 1$ for all $x$.