2
$\begingroup$

Let c, k, d $ \in \mathbb{N} $, let a, x $ \in \mathbb{N}^k $ suppose for all i $ \leq $ k, $ x_i \leq d $, $ a_i \in \mathcal{O}(d2^i) $ and $ \sum{a_ix_i} = c $ my question is for the value of c that maximizes the number of solutions to this equation, what is a tight bound for the number of solutions to this equation for said c. I know that in the related problem of the number of solutions for a given c, when the $x_i's$ are unrestrained as c -> $ \infty $ the number of solutions is roughly $ \mathcal{O}(c^k) $.

However, my intuition tells me that constraining the $x_i$'s should reduce the maximal number of solutions to roughly $ \mathcal{O}(2^k) $ for any c, since the bounds for the $ x_i's $ guarantees zero solutions after a certain point, and the bound the $a_i's$ spreads the solution over a relatively wide range.

I know this question has some relation to work done by Richard Stanley, and I'm wondering if its actually a special case of the work of him, or someone else.

I'm kind of an abstract math noob so please ask clarifying questions if part of my question seems confusing. Also please go easy on me if this is actually a really easy problem, or related to a well known result.

Improve this question
$\endgroup$
6
  • $\begingroup$ Let $k,a_i$ be fixed, and $f(c)$ denotes the number of solution to $\sum_{i=1}^k a_i x_i=c$. Then by inclusion-exclusion the number of solutions bounded by $x_i\leq d$ equals $$\sum_{A\subseteq\{a_1,\dots,a_k\}} (-1)^{|A|} f\big(c-(d+1)\cdot\sum_{a\in A} a\big).$$ $\endgroup$
    – Max Alekseyev
    Commented May 26, 2020 at 16:06
  • $\begingroup$ Can you explain please. It seems like this is using inclusion exclusion on d, but it seems like it uses f(c) in the answer since that is the term in the sum for the empty set. $\endgroup$
    – Avi Tachna-Fram
    Commented May 27, 2020 at 5:52
  • $\begingroup$ Yes, $A$ can be the empty subset, which corresponds to term $f(c)$. $\endgroup$
    – Max Alekseyev
    Commented May 27, 2020 at 7:57
  • $\begingroup$ Oh I see thats the number of solutions to the unconstrained problem, that makes sense. Thank you so much! $\endgroup$
    – Avi Tachna-Fram
    Commented May 27, 2020 at 23:35
  • $\begingroup$ Do you happen to know the asymptotics of this function in terms of a_i's, d, k? Not the f function I know that one, but the inclusion exclusion sum you gave. $\endgroup$
    – Avi Tachna-Fram
    Commented May 28, 2020 at 4:39

0

Reset to default

You must log in to answer this question.