6
$\begingroup$

From Our short paper

For polynomial $F$ with integer coefficients, define the recurrence $f(n)=F(n,f(n-1),f(n-2),...,f(n-d))$. We conjecture that $f(n)$ satisfy Somos like sequence
$f(n)=\frac{G(f(n-1),...,f(n-d_1))}{H(f(n-1),...,f(n-d_2))}$ for polynomials $G$,$H$ which do not depend on $n$.

The strong conjecture is for all $F$ and the weak conjecture is about $F$ which is linear in $f(n-i)$.

It solves special parametric cases like $f(n)=F(n,f(n-1),f(n-2))=(f(n-1)^2)(b_1 n+b_2)+f(n-2)(b_3 n+b_4)$ for all integers $b_i$ and $f(n)=f(n-1)(n^2+n+2)+f(n-2)(3 n+ 5 )$. The proofs are based on finding algebraic dependency of polynomials.

Q1 Are the conjectures true?

Added later

In comments was suggested existence of algebraic dependency not depending on $n$ using resultants of consecutive terms.

This doesn't prove the conjectures, since additional linearity "luck" is needed.

Improve this question
$\endgroup$
9
  • $\begingroup$ Remark. Recurrence $b_{n}' = n^2b_{n-1}' - \omega^2 (n-1)^2 b_{n-2}'$ appears here mathoverflow.net/a/475581/454 Maybe this method would help with it when $\omega$ is an integer.. $\endgroup$
    – Gerald Edgar
    Commented Aug 2 at 14:10
  • 2
    $\begingroup$ Not sure about the conjecture, but using algebraic dependency in the paper is an overkill. It is enough to take two polynomials representing the recurrence for two consecutive terms and compute their resultant with respect to $n$, which will give a polynomial ("algebraic dependency") not depending on $n$. It also shows that there is no option for failure in finding an algebraic dependency, however, I'm not about the "luck" of linearity for the highest term in general. $\endgroup$
    – Max Alekseyev
    Commented Aug 2 at 23:08
  • $\begingroup$ @MaxAlekseyev The paper discusses non-linearity and based on experiments it suggests to try dependency on more f(n-i). I can't reproduce your resultant result, are you sure it works? $\endgroup$
    – joro
    Commented Aug 3 at 4:51
  • $\begingroup$ What recurrence you cannot process with resultant? $\endgroup$
    – Max Alekseyev
    Commented Aug 3 at 5:08
  • $\begingroup$ @MaxAlekseyev I can't solve $f(n)=f(n-1)(n+2)+f(n-2)(3 n + 5)$ with your method. Maybe you need to add variables $y_n$,$y_{n+1}$ and take the resultant of $f(n)-y_n,f(n+1)-y_{n+1}$, but this doesn't seem linear, not sure. $\endgroup$
    – joro
    Commented Aug 3 at 5:47

2 Answers 2

Reset to default
3
+50
$\begingroup$

This is just an extended comment.

There is no need to invoke the algebraic dependency search. The recurrence can be found by directly constructing Groebner basis $B$ under any term order, in which $n$ has the highest weight and $y_m$ corresponding to $f$ with largest index has the second highest weight. Then in $B$ we are interested in polynomials with degree of $n$ equal 0 and degree of $y_m$ equal 1.

Here is a sample Sage code (updated 2024-08-06), which as an example processes the same recurrence as in Theorem 6: $$F (n, f (n-1), f (n-2)) := f(n-1)(n^2 + n + 2) + f (n-2)(3n + 5).$$

It finds 3 independent solutions of the minimal possible order 4: $$f(n) = \tfrac{-16 f(n-3) f(n-1)^{3} + 24 f(n-4) f(n-1)^{3} + 56 f(n-3) f(n-2) f(n-1)^{2} - 84 f(n-4) f(n-2) f(n-1)^{2} - 366 f(n-4) f(n-3) f(n-1)^{2} + 189 f(n-4)^{2} f(n-1)^{2} - 24 f(n-2)^{3} f(n-1) + 444 f(n-3) f(n-2)^{2} f(n-1) + 174 f(n-4) f(n-2)^{2} f(n-1) - 164 f(n-3)^{2} f(n-2) f(n-1) - 1342 f(n-4) f(n-3) f(n-2) f(n-1) + 822 f(n-4)^{2} f(n-2) f(n-1) + 1092 f(n-3)^{3} f(n-1) + 312 f(n-4) f(n-3)^{2} f(n-1) - 567 f(n-4)^{2} f(n-3) f(n-1) - 252 f(n-2)^{4} + 230 f(n-3) f(n-2)^{3} + 341 f(n-4) f(n-2)^{3} - 2004 f(n-3)^{2} f(n-2)^{2} + 2348 f(n-4) f(n-3) f(n-2)^{2} - 2338 f(n-4)^{2} f(n-2)^{2} - 4954 f(n-3)^{3} f(n-2) + 12017 f(n-4) f(n-3)^{2} f(n-2) - 3672 f(n-4)^{2} f(n-3) f(n-2) - 7888 f(n-3)^{4} + 3672 f(n-4) f(n-3)^{3}}{24 f(n-4) f(n-2) f(n-1) - 16 f(n-2)^{3} - 4 f(n-4) f(n-2)^{2} - 27 f(n-4)^{2} f(n-2) - 54 f(n-3)^{3} + 27 f(n-4) f(n-3)^{2}},$$ $$f(n) = \tfrac{24 f(n-3) f(n-2) f(n-1)^{2} - 12 f(n-4) f(n-2) f(n-1)^{2} - 186 f(n-4) f(n-3) f(n-1)^{2} + 123 f(n-4)^{2} f(n-1)^{2} - 16 f(n-2)^{3} f(n-1) + 116 f(n-3) f(n-2)^{2} f(n-1) + 34 f(n-4) f(n-2)^{2} f(n-1) - 52 f(n-3)^{2} f(n-2) f(n-1) - 322 f(n-4) f(n-3) f(n-2) f(n-1) + 122 f(n-4)^{2} f(n-2) f(n-1) - 36 f(n-3)^{3} f(n-1) + 600 f(n-4) f(n-3)^{2} f(n-1) - 369 f(n-4)^{2} f(n-3) f(n-1) - 36 f(n-2)^{4} + 90 f(n-3) f(n-2)^{3} + 3 f(n-4) f(n-2)^{3} - 300 f(n-3)^{2} f(n-2)^{2} + 324 f(n-4) f(n-3) f(n-2)^{2} - 78 f(n-4)^{2} f(n-2)^{2} - 1238 f(n-3)^{3} f(n-2) + 2055 f(n-4) f(n-3)^{2} f(n-2) - 648 f(n-4)^{2} f(n-3) f(n-2) - 1392 f(n-3)^{4} + 648 f(n-4) f(n-3)^{3}}{8 f(n-3)^{2} f(n-1) - 12 f(n-4) f(n-2)^{2} + 51 f(n-4)^{2} f(n-2) - 58 f(n-3)^{3} - 51 f(n-4) f(n-3)^{2}},$$ $$f(n) = \tfrac{4 f(n-3) f(n-1)^{2} - 3 f(n-4) f(n-1)^{2} - 2 f(n-2)^{2} f(n-1) + 10 f(n-3) f(n-2) f(n-1) - 2 f(n-4) f(n-2) f(n-1) - 14 f(n-3)^{2} f(n-1) + 9 f(n-4) f(n-3) f(n-1) - 3 f(n-2)^{3} + 16 f(n-3) f(n-2)^{2} - 18 f(n-4) f(n-2)^{2} + 9 f(n-3)^{2} f(n-2)}{2 f(n-3) f(n-2) - 3 f(n-4) f(n-2) + 3 f(n-3)^{2}},$$ the last of which matches the one given in the paper.

ADDED. Since there is an interest in a faster code avoiding computation of Groebner bases, here is another Sage code, which treats each term $n^uy_m^v$ as a variable and uses linear algebra to nullify the coefficients of such terms, except for $(u,v)=(0,0)$ and $(u,v)=(0,1)$. In general, it does not guarantee to produce solutions of the smallest possible order, but in turn it works much faster than the first code. For the recurrence quoted above, it happens to also produce a solution of the minimal order 4.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Many thanks for the answer and the sage code! You have typo in the definition of F: (n2+n+2) should be n^2+n+2. I am still using the dependency approach. Set $f(n-2)=f_2,f(n-1)=f_1$ and using iterates of $F$ I compute $f(n),f(n+1)...f(n+d_3)$. If $d_3$ is large, I get many algebraic dependencies. Some of them are lucky and some of them are not lucky. If I work with the $b_i$ as variables, this would give parametric solution, but it is slow for my implementation :( $\endgroup$
    – joro
    Commented Aug 5 at 3:06
  • $\begingroup$ @joro: Typo is corrected, thanks. The direct approach in my answer should have a better performance. One can easily introduce additional parameters (variables) if needed. Furthermore, for a chosen order it guarantees to find a "lucky" solution if one exists. $\endgroup$
    – Max Alekseyev
    Commented Aug 5 at 3:47
  • $\begingroup$ If I add .groebner_basis(deg_bound=2) to your code, this produces sage internal error, the bug report is at: groups.google.com/g/sage-devel/c/pWolJm0JrUg $\endgroup$
    – joro
    Commented Aug 5 at 8:41
  • $\begingroup$ I added an answer, working with linear algebra instead of working with Groebner basis. $\endgroup$
    – joro
    Commented Aug 6 at 14:52
  • $\begingroup$ Thanks. Just for the record about ADDED, linear algebra approach is investigated in my earlier answer $\endgroup$
    – joro
    Commented Aug 7 at 5:43
0
$\begingroup$

I am investigating Groebner basis free approach, using only linear algebra.

This might be more human friendly, since linear algebra is more intuitive than the heavy machinery of Groebner basis.

Set $f(0)=x_0,f(d-1)=x_{d-1}$ and $f(d)=F(d,x_{d-1}...)$ $f(i)$ is polynomial in $n$ and $x_i$. Assume the order of the solutions is $d_3$ and $D=\max(\deg(G),\deg(H))$ Assume solution $f_{d_3}=G/H$ exist. Write $G=\sum a_{i,G} X_i,H=\sum a_{i,H} X_j$ where $X$ is monomial in $x_i,n$. The number of monomials $X$ is $\binom{d_3+D+1}{d_3}$. If an oracle (in our case the Groebner basis) gives candidate $a_i$, we can verify if it is really solution by computing iterates of $F$. Trying to avoid the Groebner basis, set the $a_i$ as variables, set the initial terms $x_i$ as constants and numerically compute $T := f_{i+d_3} H - G$. This is linear in the variables $a_i$ and the monomials $X_i$ are constants. Overdetermine the linear system $T$ by computing many $f(i)$. Overdetermining is important, because the dependency must hold for polynomials, not only integers. Solve the linear in $a_i$ using linear algebra. I tried this computationally and it works, but is slower than Groebner basis.

If someone experiment with this approach, have in mind that $f(i)$ might grow doubly exponential or something like $n^n$, so instead of the integers, I work over finite field of size less than $2^{28}$, because the CAS sage is significantly faster.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I've updated my answer with a code that does not use Groebner bases. Please check it out. $\endgroup$
    – Max Alekseyev
    Commented Aug 6 at 19:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .