All Questions
Tagged with decidability co.combinatorics
4 questions
1
vote
0
answers
151
views
Decide if a group is abelian
Let $G = \langle X: R\rangle$ be a finitely presented group. The following problem seems very natural to me, yet I cannot find any reference for it: Decide if $G$ is abelian or not.
With a reduction ...
8
votes
2
answers
262
views
Congruences of binomial sums
Let $a_n$ is a binomial sum, for example
$$
a_n := \sum_{k} \binom{n-k}{k} \quad \text{or} \quad \sum_{k=0}^n\binom{n+k}{n-k}\binom{2k}{k}
\quad \text{or} \quad \sum_{k=0}^n\sum_{\ell=0}^k\binom{n}{k}\...
2
votes
1
answer
146
views
Recognizing parallelogram tilings from their vertex set
Suppose I have a tiling of the plane with parallelograms where the sides of the parallelograms come from a specified finite set of vectors. If I only have access to the vertices of this tiling I may ...
18
votes
4
answers
1k
views
Proving univariate polynomials (defined by sums, binomial coeffs, etc.) are nonnegative: is it 'routine'?
My colleagues and I are working on a project related to an old paper of C. Borell and we have boiled it down to the following problem:
Show, for all integers $1 \leq i \leq k$, that the univariate ...