Can we give a bound on any associative function?

90 Views Asked by At

We say that $f:[1,\infty)^2\to[1,\infty)$ is associative if $$f(f(a,b),c)=f(a,f(b,c))$$ And symmetric if $$f(a,b)=f(b,a)$$

e.g. the arithmetic operations '+' and '$\cdot$' are associative and symmetric.

Can we give a bound $b:[1,\infty)^2\to[1,\infty)$ (which might not be associative) such that every associative function $f$ satisfies $$\exists c\:\forall x,y\in [1,\infty): f(x,y)\leq c\cdot b(x,y)$$

,

If not, can we find such bound on every associative and symmetric function?

2

There are 2 best solutions below

9
On

Proffering the following argument aiming to prove that no such function $b$ can exist.

Assume contariwise that such a function $b$ exists.

Let $D$ be a set of representatives of cosets of the (multiplicative) subgroup $\Bbb{Q}^*_{>0}$ of $\Bbb{R}^*_{>0}$. Note that if $d\in D$ we can always replace $d$ by $10d$, if we so desire. So without loss of generality we can assume that $D\subset [1,\infty).$ Because $D$ is uncountable, we can set a side a countably infinite subset $$ N=\{d_0,d_1,d_2,\ldots\}\subseteq D. $$ We then replace $D$ with the set $$ D_b=(D\setminus N)\cup\{d_i10^{k_i}\mid i\in\Bbb{N}\}, $$ where the exponents $k_i$ are integers selected in such a way that $$d_i10^{k_i}>10^ib(1,d_i)$$ for all $i\in\Bbb{N}$. Observe that $D_b$ is still a set of representatives of cosets.

Given such a set $D_b$ we define a function $f:[1,\infty)\times[1,\infty)\to D_b$ by declaring that $f(a,b)=d\in D_b$ where $d$ is the unique number in $D$ belonging to the coset of $ab$. This function is both associative and symmetric, because $f(f(a,b),c)$ and $f(a,f(b,c))$ are both equal to the uniquely determined $d\in D_b$ with the property that $abc$ is a rational multiple of $d$.

For any natural number $n$ we then also have $$ f(1,d_n)=10^{k_n}d_n>10^nb(1,d_n). $$ This means that no constant $c$ will work for this particular choice of an associative $f$, because $10^n>c$ for some choice of $n$.

So essentially I took the multiplication, but I replaced the correct product with its more or less arbitrary rational multiple. Or, the ratio $f(a,b)/ab$ is always a rational number. The key is that by selecting the multiples carefully we won't break associativity.

Mind you, this argument may depend on the Axiom of Choice. Otherwise sets like $D$ may not exist.


A less general but easier to follow attempt at construction is to use suitable bijections to port an associative algebraic structure. Let $\phi:[1,\infty)\to[1,\infty)$ be any bijection. Then the function $$ f(a,b)=\phi^{-1}(\phi(a)\cdot\phi(b)) $$ is easily seen to be associative, because both $f(f(a,b),c))$ and $f(a,f(b,c))$ are equal to $\phi^{-1}(\phi(a)\phi(b)\phi(c))$.

Consider the following function $\phi:[1,\infty)\to[1,\infty)$ $$ \phi(x)= \begin{cases} 10^n,&\quad\text{if $x=2^n$ for some natural number $n$,}\\ 2^n,&\quad\text{if $x=10^n$ for some natural number $n$,}\\ x,&\quad\text{otherwise}. \end{cases} $$ So if $n$ is an odd natural number and $a=b=2^{n/2}$, we get $$ f(a,b)=\phi^{-1}(\phi(a)\phi(b))= \phi^{-1}(2^{n/2}\cdot2^{n/2})=\phi^{-1}(2^n)=10^n. $$ So for these values of $a,b$ we get $f(a,b)=5^nab$ where we can choose $n$ to be any odd natural number (so arbitrarily large). This is a counterexample to many a bound $b(x,y)$, for example to the bound $b(x,y)=(x+y)^2$ the OP asked about in a comment.

5
On

There exists no such $b$ even if $f$ is symmetric and associative.Let $f(x,y)$ be defined by $$f(x,y)=[(b(x,y)+b(y,x)+1).e^{x+y}]+1.1$$ where $[.]$ is greatest integer function if both $x$ and $y$ are natural numbers and $f(x,y)=1.1$ if any one of $x$,$y$ fail to be a natural number.Notice that $f(f(x,y),z)=f(x,f(y,z))=1.1$ for all $x,y,z$ since $f(x,y)$ is always not a natural number.It is easy to see that $f$ is symmetric.There exists no $c$ such that $f(x,y)/b(x,y)\leq c \forall x,y$ since $f(n,n)/b(n,n)$ tends to infinity.