Let's take a look at this simple task (Pythagorean Triples):

Calculate $A$ and $B$ such that $A^2 + B^2 = C^2$.

$C$ is given.

Is there any way to find an upper bound for $A$, $B$, $A^2$, and $B^2$?

The upper bound will be a function of $C$.

$0 < A < f_1(C)$

$0 < B < f_1(C)$

$0 < A^2 < f_2(C)$

$0 < B^2 < f_2(C)$

$f_1(C) = ?$

$f_2(C) = ?$

Any ideas?

  • $\begingroup$ I don't know how precise you need your bound. But if you only need an explicit upper bound: Can $A$ be equal or bigger than $C?$ Can $A^2$ be equal or bigger than $C^2?$ $\endgroup$ – mfl May 22 '14 at 14:46
  • $\begingroup$ @ManuelFdzLpz - you are right, these are the trivial upper bounds. I'm looking for the tightest bounds, I forgot to mention it. $\endgroup$ – Mockingbird May 22 '14 at 14:56
  • $\begingroup$ Since $(3,4,5)$ is a Pythagorean triple the best bound you can find is $A<C-1,B<C,$ assuming $A< B.$ For the squares, $A^2<C^2-15,B^2<C^2-8.$ $\endgroup$ – mfl May 22 '14 at 15:02
  • $\begingroup$ Is there something more generic for the squares? $\endgroup$ – Mockingbird May 22 '14 at 15:05

Note that $3,4,5$ is a triple and $n^2-1,2n, n^2+1$ is also a triple.

Your upperbound must satisfy $$f(n^2+1) > n^2-1$$

So if you are looking for a "nice function" (Polynomial), the best upperbound must satisfy $f(C) \geq c-2$ infinitelly often, and you can make it $C-1$. To replace $C-2$ by $C-1$ you just observe that $k,n,n+1$ is a solution whenever $k^2=2n+1$, that is whenever $n=\frac{m^2-1}{2}$ for $m$ an odd integer.

Moreover, these functions yield $\leq$ not strict inequalities. If you want strict inequalities, there is no best polynomial upperbound. You might want your function to only take integer values.

If by function you mean any function, then the answer is simple: your problem is the definition of your function. And again, since all your variables are integers, there is no best upperbound to satisfy your strict inequalities, unless again you restrict the codomain to integers.

  • $\begingroup$ A,B and C are integers. The function above won't change a lot (I'm working in a binary representation for integers and the bounds are important, so C-1 bound is almost like C bound). The bounds for A^2 and B^2 are much more imporant BTW. $\endgroup$ – Mockingbird May 22 '14 at 15:05
  • $\begingroup$ BTW I think you are wrong about the A,B bounds. Check that triplet A=19, B=180, C=181. The bound for A and B is really C-1. What about the bound for A^2 and B^2 ? $\endgroup$ – Mockingbird May 22 '14 at 15:08
  • $\begingroup$ @Mockingbird The point is that no matter what upperbound you'l find, when $C=n^2+1$ you will have $f(C) > C-2$. And that happens infinitely often. The bound cannot be improved at those points. $\endgroup$ – N. S. May 22 '14 at 15:08
  • $\begingroup$ Neither for the squares? (A^2 and B^2) $\endgroup$ – Mockingbird May 22 '14 at 15:09
  • 1
    $\begingroup$ @Mockingbird Yes you are right, you can actually make $F(C)=C-1$ infinitelly often. Moreover, again, you have infinitely often $A^2 \geq (C-1)^2$.... The best polynomial upperbound you can find for $A^2$ is $(C-1)^2$. $\endgroup$ – N. S. May 22 '14 at 15:10

There are an infinite number of pythagorean triples for which $B + 1 = C$. Let $A = 2n+1$. Let $B = 2n^2 + 2n$ and $C = B + 1 = 2n^2 + 2n + 1$.

$$\begin{align} \\ A^2 + B^2 &= (2n+1)^2 + (2n^2 + 2n)^2 \\ & = (4n^2 + 4n + 1) + (4n^4 + 8n^3 + 4n^2) \\ & = 4n^4 + 8n^3 + 8n^2 + 4n + 1 \\ & = (2n^2 + 2n + 1)^2 \\ & = C^2 \end{align} $$


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.