Ask Your Question

Running a search algorithm

asked 2021-10-01 19:03:12 +0100

mathstudent gravatar image

I want to write a program to check whether a given rational function $f(x,y)$ in two variables $x,y$(=$\dfrac{\text{polynomial in } x,y}{\text{polynomial in }x,y}$) is of the form $\sum_{i_k,j_k,l_k,m_k}\dfrac{1+x^{i_k}+y^{j_k}}{1+x^{l_k}+y^{m_k}}$ where $i_k,j_k,l_k,m_k$ runs from $0$ to $5$(say), and $k=$number of summands is $16$(say).

Is there a way to run a for loop that checks this? The main problem for me is that there are too many variables involved.

edit retag flag offensive close merge delete


Could you please provide a concrete example of the fractions you want to deal with, so that we get an idea of their structure, their degree, etc ?

tmonteil gravatar imagetmonteil ( 2021-10-05 18:12:45 +0100 )edit

3 Answers

Sort by ยป oldest newest most voted

answered 2021-10-04 16:10:23 +0100

Max Alekseyev gravatar image

updated 2021-10-05 15:44:50 +0100

You can speed up things by factoring the denominator of $f(x,y)$ and see if for each factor you can find its multiple of the form $1+x^l+y^m$ - these will give you candidate denominators in the decomposition. Given that $1+x^l+y^m$ is irreducible (over $\mathbb{Q}$ at least), each factor must simply be of this form.

edit flag offensive delete link more

answered 2021-10-03 15:47:37 +0100

Emmanuel Charpentier gravatar image

updated 2021-10-03 18:23:26 +0100

A "brute-force" approach to this problem is doubtful :

Such an approach would generate all possible sum of 16 terms, each representing one quadruplet $i, j, k, l \in \{0, \dots, 5\}$. Since there are $6^4=1296$ such potential summation terms, there are ${6^4}^{16}$ possible 16-terms sums.But :

sage: ((6^4)^16).log(10).n()

meaning that the number of sums is about $6.44\cdot 10^{49}$, which seems a bit too large for systematic exploration...

Limiting the size of the exploration by other means is necessary. But this is the feathers of a totally different horse...

HTH, but doubting it,

edit flag offensive delete link more

answered 2021-10-01 21:19:24 +0100

tmonteil gravatar image

Prehaps coud itertools.product be of some help:

from itertools import product
P = product(range(6), repeat=4)
for i,j,k,l in P:
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2021-10-01 19:03:12 +0100

Seen: 294 times

Last updated: Oct 05 '21