0
$\begingroup$

Let $k$ and $s$ be natural numbers such that $s^2-s+1 \equiv 0 \pmod{k}$. Consider the equation $$ -si+(s-1)j \equiv 0 \pmod{k} $$

In all examples of pairs $(s,k)$ that I've tested, I got $(i+j)^2>k$ for every solution with $0<i,j$. Is there a way to establish such a bound? Alternatively, can one prove that there is no positive solution with $i+j <\sqrt{k}$?

This problem comes from searching for invariant polynomials in two variables under a diagonal group action. I'm trying to bound the degree of a invariant monomial $x^iy^j$ from below.

$\endgroup$
  • 1
    $\begingroup$ The displayed equation is equivalent to $$i\equiv sj\pmod k$$ $\endgroup$ – Barry Cipra Jul 6 '16 at 5:53
1
$\begingroup$

Note that $s^2-s+1\equiv0$ mod $k$ can be rewritten in two ways:

$$s(s-1)\equiv-1 \mod k$$ and

$$s^2\equiv s-1\mod k$$

The first rewriting shows that $s$ is invertible mod $k$, which means the congruence

$$si\equiv(s-1)j\equiv s^2j \mod k$$ (where we've used the second rewriting) simplifies to

$$i\equiv sj\mod k$$

Squaring this gives

$$i^2\equiv s^2j^2\equiv(s-1)j^2=(sj)j-j^2\equiv ij-j^2\mod k$$

or

$$i^2-ij+j^2\equiv0\mod k$$

which means that $k$ divides $i^2-ij+j^2$. Now if $i$ and $j$ are positive integers satisfying this congruence, then $i^2-ij+j^2=(i-j)^2+ij$ is a positive number, hence cannot be less than $k$. Consequently

$$k\le i^2-ij+j^2\lt i^2+2ij+j^2=(i+j)^2$$

$\endgroup$
1
$\begingroup$

As noted in the comments, because $s$ satisfies $s^2-s+1\equiv0\pmod{k}$ we have $$-si+(s-1)j\equiv0\pmod{k}\qquad\Leftrightarrow\qquad i\equiv sj\pmod{k},$$ as $-s(s-1)\equiv1\pmod{k}$. So if $i,j>0$ then $s>0$, and $$(i+j)^2\geq(sj+j)^2=(s+1)^2j^2=(s^2+2s+1)j^2,$$ where $s^2+2s+1>s^2-s+1\geq k$. Hence $i+j>\sqrt{k}$.

$\endgroup$
  • 1
    $\begingroup$ How do you get from the congruence $i\equiv sj$ to the equality $(i+j)^2=(sj+j)^2$? For example, if $s=10$, $k=13$, and $j=4$, then $i=1$ solves the congruence, not just $i=40$. $\endgroup$ – Barry Cipra Jul 6 '16 at 12:05
  • $\begingroup$ You are absolutely right, let me give it some thought. $\endgroup$ – Inactive - Objecting Extremism Jul 6 '16 at 13:47
  • 1
    $\begingroup$ Sorry, I still don't think that's right. In the example I gave, $(i+j)^2=(1+4)^2=25$, while $(sj+j)^2=(10\cdot4+4)^2=44^2=1936$. $\endgroup$ – Barry Cipra Jul 6 '16 at 16:03

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.