Yes, BM is for fixed coefficients. I overlooked that you want something more complex. To be clear: is that $q^n$ and your keyboard is producing circumflex accents instead of carets, or is it something else?

Berlekamp-Massey.

@DavidESpeyer's family $(ku, k^3-ku)$ covers all solutions to $a+b = \gcd(a^3, b^3)$ but that doesn't seem to be explicitly stated yet in this comment thread.

Is this not algebraically identical to the question linked by Johannes?

The left hand side appears to satisfy the D-finite recurrence $${(n-3)(n-1)n(n+1) a(n)} = {4n(2n-1)(4n^2-17n+16) a(n-1)} -{32(n-2)(2n-5)(2n-3)(2n-1) a(n-2)}$$ The second double sum (without the binomial weight) appears to have a D-finite recurrence with quadratic coefficients, which would explain why @CarloBeenakker didn't find a closed form.

I don't know how much it helps, but on the right hand side the first sum can be removed entirely if the limit of $\ell$ in the final sum is increased to $m$ instead of $m-1$.

In general, $p(\vec{x})=q(\vec{x})$ implies $r(p(\vec{x}), q(\vec{x}), \vec{y}) = r(q(\vec{x}), p(\vec{x}), \vec{y})$. By using $r_i$ of arity four or more we can generate arbitrarily many lower bounds on a pair of equations, and in general there's no reason to suppose that these lower bounds are mutually comparable.

You have least and greatest elements $x=x$ and $x=y$, so the question is whether two elements can have multiple incomparable common maximal lower / minimal upper bounds.

The official advice on cross-posting says to wait several days before cross-posting. 29 hours is not several days.

@Connor, on close reading your first comment contradicts itself and the question. If the aim is to minimise $\sum_r \max_c (\sigma_r(c) + \tau_c(r))$ then the answer to Sam's comment isn't "Yes", and the sum can't be as small as $|R| + 1$ in the case of a square, unless the square is $1 \times 1$. Please edit the question to express clearly what you actually want to ask about.

There's a trivial lower bound $\max(|R|, |C|) + 1$. It should be straightforward to adapt the argument for a square to achieve this lower bound.

Empirically it seems to be pentagons. Out of $1000$ trials of $5m$ chords for $m \in [1, 20]$ pentagons took the lead at $20$ chords with $416$ wins (vs $395$ for quadrilaterals), and by $100$ chords they were winning more than $80\%$ of trials, with quadrilaterals picking up the rest.

If the arbitrary edges removed are between $(1, m_i)$ and $(1, m_i + 1)$ then they are irrelevant to the escape paths sought, so by symmetry this should be a counterexample.

More recently than that it was featured in a British newspaper's puzzle column.