0

Is it possible to determine, given pairs $\{m_1, M_1\}$ and $\{m_2, M_2\}$, where $m_n \le 0$, $M_n \gt 0$ and $\{m_n, M_n \in \mathbb{Z}\}$, which pair $\{m_1, M_2\}$ or $\{m_2, M_1\}$ will have the smallest and largest product, WITHOUT actually comparing the products, doing division or using a log function?

I was thinking that given: $a \le b \le c$ that $ab \le bc$ where $\{a, b, c \in \mathbb{N}\}$, I could use it somehow, but I've been stuck on this for a week without success.

I've seen this question Determining which number pair has greater product - without multiplying., and it sounds similar, but I'm not entirely sure.

Community
  • 1
Adrian
  • 191
  • you will have to rank the 4 numbers – Argyll May 31 '16 at 04:53
  • No, you can not, in general. If |m1| and M1 are both less than |m2| and M2 (and vice versa) this is trivial, but otherwise it depends upon the proportions of the values and you can't compare those without multiply or dividing. – fleablood May 31 '16 at 04:55
  • Knowing things like $m_1+M_1=m_2+M_2$ gives simplifications - and I would imagine that other constraints can help out too - but, in general, the condition $m_1M_1\geq m_2M_2$ is not something that can be expressed in the language of the order on $\mathbb R$ alone (or even with the order and addition - multiplication is really crucial) – Milo Brandt May 31 '16 at 04:58
  • Can you please expand your suggestion @Argyll? – Adrian May 31 '16 at 05:03

2 Answers2

3

Your statement that you propose works for certain cases, but not all. In particular, if

$$0 \leq a \leq b \leq c,$$

Then because we are only multiplying positive numbers,

$$b \times c \geq b \times b \geq b \times a.$$

If $a < 0 \leq b \leq c,$ Then because $$a \times b \leq 0 \leq b \leq b \times c,$$

your suggested statement holds as well. However, if

$a \leq b < 0 \leq c,$

Then because $b \times c \leq 0$ since $ b <0 \wedge c \geq 0.$ and since $a \times b > 0$ since $a \leq b < 0,$ Then in this case

$$a \times b > 0 \geq b \times c.$$

Thus, you will need to consider some of these aspects of the product (in particular some of the sign switching) on a general case-by-case analysis. As an exercise, I recommend seeing what happens when $a \leq b \leq c < 0.$

Eric
  • 163
  • I was thinking that I could negate the $m_n$ values, which would invert the ordering relative to each other, and then compare the $m_n$ values against the $M_n$ values to magically come to a solution. So are you saying that is not possible? – Adrian May 31 '16 at 05:02
  • @Adrian : You might as well negate the $m_n$ values since, as is, each product is either negative or zero and dealing with the three "something is zero" cases is straightforward, and the "everything is negative" is trivial to recast in terms of positive $m_n$s. – Eric Towers May 31 '16 at 05:06
  • @EricTowers, no, I don't think so. The ordering is only between ${ m_1 \lt M_1 }$ and ${ m_2 \lt M_2 }$. I don't think it would help. Casting $m_n$s to negative, would invalidate this, unless there's some other constraint that would be of use. – Adrian May 31 '16 at 05:16
  • @Adrian : You've given the $m_n \leq 0$ and the $M_n > 0$. Except for $m_1=0$, $m_2= 0$, or $m_1 = m_2 = 0$, these products are negative and ordering them with or without their signs is straightforward. – Eric Towers May 31 '16 at 05:21
1

If either or both of your $m_n$ is $0$, this is pretty straightforward, so let's move on with no variables potentially zero.

Consider points in the second quadrant. These points have $x < 0$ and $y > 0$. Curves of constant product $xy=c$ as $c$ varies in $(-\infty, 0)$ are single branches of hyperbolae with center at $0$, vertices on the line $y = -x$, and asymptotes along the coordinate axes. Your question is equivalent to determining which of $(m_1, M_2)$ and $(m_2, M_1)$ is on the branch with vertex closest to the origin.

You seem to want to limit us to linear operations: addition, subtraction, and some multiplication. There is no hope of distinguishing all these curves with bounded numbers of such operations. If there were upper bounds on the $m_n$ and the $M_n$, then we could construct piecewise functions separating these branches. (Quickly requiring many, many pieces.) This would give, for example, a set of inequalities that are all satisfied for integer points whose coordinate product is $>-7/2$ or all violated for integer points whose coordinate product is $<-7/2$ and then similarly for every other half integer. Then we could binary search through these separators to determine which (if any) discriminate between $(m_1, M_2)$ and $(m_2,M_1)$.

For large products, these branches are very close together -- it will require many, many very nearly identical inequalities to separate them.

At some point, this becomes stupid. Multiply, compare, done.

Eric Towers
  • 67,037