3
$\begingroup$

I found a new kind of identities which are half logic and half algebraic while working on a proof of NP-completeness. They are like this: $$ \frac{a+mb}{n+m} < \frac{a}{n} \iff b < \frac{a}{n} $$ It's the first time, I encounter such an identity. It has the amusing and counter-intuitive property that the right member is not modified, but the two left members are not algebraically equivalents.

Can you tell me if you ever encountereed such identities before? These ones in particular? (There are 9 in total: equality, strict inequality or not, changing way if $n+m$ and $m$ have same sign or not.) If not would you have suggestions for naming this kind of identities?

Moreover it would be interesting to know if there is a finite number of identities of this kind, an infinite number but recursively enumerable, etc.

I do not ask for a proof [!] but only whether somebody knows of a systematic treatment of equivalences of this kind in the literature.

Feel free to search one but let me a few months to search by myself. If I don't have any idea to prove it, I'll update my question to let you know anyone is welcome to publish on the subject.

Update 2013/07/26:

egreg definitely found the good idea behind these identities. Let me update my question as follows : Does there exist an identity of the type $$ a ? b \iff a ? f(a,b) $$ where f(a,b) is not a weighted mean of a and b (? may be =, <, >, <=, >=)?

Update 2013/07/30:

Thanks to zyx we now have a very simple way to construct an infinity of such identities. There remains a "few" questions:

Since it doesn't appear anyone know an article or a book that explicitely remarked these kind of identities as particular, would you have suggestions for naming this kind of identities? (Question A)

Are all such identities as zyx described (in the meaning $(b-a)^n \times \dots$)? (Question B) If not, are these identities recursively enumerable? (Question C)

What are the examples of such identities that are important, useful for demonstrating mathematical results? (Question D) We already know that these identities from weigthed means are useful. Do you have other examples from classical proofs? (Question D')

Note that the answer to question B is no if you change (or extend) the rules ;). For example on rings instead of fields and if the inequality may be strict or not in the same identity. As an example, if we take the ring $2\mathbb{Z}$ of even integers, we have the identity $$b < a \iff (b-a)^3 + 8 + a \leq a.$$

So far, I only had the following idea for naming this kind of identities: "semi-invariant identities". It shouldn't be hard to find a better name.

Update 2013/07/31 Clarification :

For now, I would like to answer the previous questions on fields only BUT the final word on these identities is out of reach. Why?

The broader framework I see for these identities is the framework of universal algebras. Given such an algebra $\mathcal{A}$ of domain $A$ and two binary relations $?_1$ and $?_2$ on $A$ such that $?_1$ and $?_2$ are orders or equivalence relations (yes, you can mix an equivalence relation and an order relation if you want but I have no idea if it could yield something interesting on some algebra), the idea is to study the identities that are as follows:

Let $n\in \mathbb{N}$, an $n$-$?_1$-$?_2$-semi-invariant identity on $\mathcal{A}$ is defined by three terms $f_1$, $f_2$, $f_3$ on $\mathcal{A}$ such that: $$\forall (a_1, \dots, a_n) \in A^n, f_1(a_1, \dots, a_n) ?_1 f_2(a_1, \dots, a_n) \iff f_1(a_1, \dots, a_n) ?_2 f_3(a_1, \dots, a_n)$$ where $f_2$ and $f_3$ are not algebraically equivalents (as I noted in the original question).

Clearly, this is too broad to ask a question in this framework right now. These identities may be interesting on algebras used to construct graphs, etc. But not many people would see an interest in it or see what I'm talking about. I would like to see what can be useful with these identities on the most standard algebras (fields is a good starting point) and it could benefit to many people not only a few dozens of specialists of some particular research domain. Following part of zyx idea, one could go even further by considering arbitrary relations.

$\endgroup$
  • $\begingroup$ Are $m,n$ natural numbers? $\endgroup$ – Pedro Tamaroff Jul 25 '13 at 17:55
  • $\begingroup$ I found the identities with m and n as natural numbers first but it is valid for reals also as long as you don't divide by zero. The identity with equality is valid on any field. $\endgroup$ – Laurent Lyaudet Jul 25 '13 at 21:09
  • $\begingroup$ I think the proper naming and context for your problem is that of homomorphisms, and faithful homomorphisms, between structures with some relations. $\endgroup$ – zyx Jul 30 '13 at 19:25
  • $\begingroup$ I think homomorphisms, and faithful homomorphisms isn't the good naming and context (Please, have a look at my update). If you can explain why you consider it a good naming and context and if you still have this opinion after reading my update, please do explain your point of view. $\endgroup$ – Laurent Lyaudet Jul 31 '13 at 19:05
7
$\begingroup$

There is nothing too mysterious about this. $$\frac{{a + mb}}{{n + m}} < \frac{a}{n} \Leftrightarrow a + mb < a + \frac{m}{n}a \Leftrightarrow mb < \frac{m}{n}a \Leftrightarrow b < \frac{1}{n}a \Leftrightarrow b < \frac{a}{n}$$

assuming $m,n>0$. For an insight, you're assuming that for each $m$, we have $$\frac{{mb + a}}{{n + m}} < \frac{a}{n}$$

as $m\to\infty$, the LHS goes to $b$. This means that $$b \leqslant \frac{a}{n}$$ But it cannot be the case $b=a/n$, because then we would get the absurdity $a<a$ from the original inequalirt. Of course, this is pushing things a little too much, since it this case we can easily manipulate the inequality. But maybe this interests you:

THM Suppose that $x,y>0,a$ are such that, for each $n\geq 1$ $$a\leq x\leq a+\frac yn$$ Then $x\leq a$, that is $x=a$.

P Assume to the contrary that $x>a$. Then $x-a>0$. Then there exists $m$ such that $m(x-a)>y$, so $x-a>\dfrac ym$, that is $x>a+\frac ym$, contradicting our hypothesis.

$\endgroup$
  • $\begingroup$ I know the proof is trivial. You can write it directly like this (? may be < > or = as I said) : (a +mb)/(n+m) ? a/n <=> n(a+mb) ? (n+m)a <=> nmb ? ma <=> b ? a/n. Thanks anyway. $\endgroup$ – Laurent Lyaudet Jul 25 '13 at 21:16
4
$\begingroup$

Assuming $m,n>0$, if you set $c=a/n$, then the condition becomes

$$ \frac{mb+nc}{m+n}<c \qquad\text{if and only if}\qquad b<c. $$

This shouldn't be surprising, because $$ \frac{mb+nc}{m+n} $$ is a weighted average of $b$ and $c$, so it lies between them.

$\endgroup$
  • $\begingroup$ Thanks I didn't see that. It makes it really clear. $\endgroup$ – Laurent Lyaudet Jul 25 '13 at 21:20
1
$\begingroup$

update my question as follows : Does there exist an identity of the type
$$ a?b \iff a?f(a,b)$$ where $f(a,b)$ is not a weighted mean of a and b (? may be =, <, >, <=, >=)?

Sure. Let $g(x,y)$ be a function that always has the same sign as $y$, and $$f(a,b)= a + g(a,b-a).$$

All ?-preserving $f(a,b)$ can be constructed in that way.


(Edit, after the update with $f_1, f_2$ and $f_3$)

The generalization has similar solutions, on the same principle. Suppose the relations $?_1$ and $?_2$ are equal. For the question to be nontrivial one would need the set of $x$ for which $a?x$ holds, to have more than one element for some $a$. But then we could take, for each $a$, any map $m(x)$ of this set to itself, and gather the maps into one function $M(a,x)$. Our $x$ is a function ($f_2$) of $a$, so in fact we have a function $F(a)=M(a,f_2(a))$ such that $(\forall a) a ? f_2(a) \iff a?F(a)$ .

Allowing the two relations to be different loosens the problem further and now one can use $a$-dependent coordinate changes. For example, in plane geometry, let $?_i$ be "is separated by distance at most $i$ from". Then $a ?_1 f(a)$ if and only $a ?_2 g(a)$, where $g(a)$ is the point twice as far from $a$ as $b$, in the same direction.

The issue, that I think will be hard to remove while keeping the format of the identity, is that the idea of $aRb = aRc$ is simply "another solution" (of a condition satisfied for fixed $a$) and as far as that is true it leads to transformations of the solution space, which is a well explored theme. It is a rich theme but not a new one.

The equation $aR_1 b = c R_2 a$, with $c$ determined from $b$, is similar to the concept of an intertwiner. We could write $R_2$ in the opposite order by taking the opposite relation, and then it is close to what you wrote down in the generalized problem.

$\endgroup$
  • $\begingroup$ While this is indeed sufficient to find new examples of such identities with inequalities on $\mathbb{R}$, I fail to see why it is necessary. If you take a field without order ($\mathbb{F}_{31}$ for example) and search for all such identities with equalities, why should they satisfy $f(a,b)=a+g(a,b−a)$ where $g(a,0) = 0$ for any a. I fail to see why it can be a function g(a,b-a) instead of g(a,b) in any case. I may be missing some trivial argument. $\endgroup$ – Laurent Lyaudet Jul 29 '13 at 18:47
  • $\begingroup$ Indeed you can always have b from a and b-a but still, your presentation suggests that it should be something like $(b-a)^n \times f(a,b)$. Eliminating such trivial cases, there may still be interesting examples. The idea is to find some kind of "kernel" of such identities. How they can be constructed, classified, etc. $\endgroup$ – Laurent Lyaudet Jul 29 '13 at 19:07
  • $\begingroup$ It is necessary and sufficient for faithful preservation of all the relations at once, which is equivalent to f.p. of equality and either of the inequalities. For f.p. of equality only, a necessary and sufficient condition is the same expression but with $g(x,y)$ equal to zero if and only if $y=0$. For inequality alone, I haven't thought about it, but it may be equivalent to what I wrote under a continuity assumption. In each case, setting $G(p,q) = f(p,q+p) - p$ translates between one form and the other. $\endgroup$ – zyx Jul 30 '13 at 18:00
  • $\begingroup$ Thanks but try to go further than trivial answers. I didn't asked for faithful preservation of all relations at once. I was saying in my original question "changing way if n+m and m have same sign or not" that reversing the inequality would still be considered as an exemple of this kind of inequalities. I didn't repeated this for simplicity in the update. Moreover the true question is "what did you mean by $g(a,b-a)$?". Since $f(a,b) = a + f(a,b) -a = a + g'(a,b) = a + g(a,b-a)$ is always true for some $g$, we need to know how to construct $g$. I updated my question to explicit the questions. $\endgroup$ – Laurent Lyaudet Jul 30 '13 at 18:23
  • $\begingroup$ By g' I didn't mean the derivative of g, read h(a,b) instead. $\endgroup$ – Laurent Lyaudet Jul 30 '13 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.