2
$\begingroup$

Consider two d-uplets $u = (u_1,...,u_d)$ and $v = (v_1, ..., v_d)$ both living in $\mathbb{N}^d$ with $d$ a positive integer. They both verify $$(*) \sum_{i=1}^d u_i = \sum_{i=1}^d v_i = k$$ with $k$ a positive integer, $k\geq d$ supposed to tend to infinity later on. Given a constant $c \in \mathbb{N}$ such that $c<k$ ($c$ could also depend on $k$, e.g. $ c= \lceil k/d \rceil$), I would like to upper bound the cardinal of the following sets: $$\{(u,v) | u \neq v, (*), \sum_{i=1}^d |u_i -v_i| \leq c \}. $$

It could also be written as bounding the cardinal of the set $$\{ u | u \neq v, (*), \sum_{i=1}^d |u_i -v_i| \leq c \} $$ for any $v$.

My knowledge of combinatorics is very low, I'd be glad to receive any reference or idea that could lead to the solution of this problem or similar ones. I do not even have intuition for the magnitude order of this quantity.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ If we assume that $k$ is sufficiently large, $c$ is sufficiently small, and $v$ is sufficiently far from the edges then we can ignore edge effects; this is equivalent to relaxing $\mathbb{N}^d$ to $\mathbb{Z}^d$, and works fine for upper bounding $|\{ u : (u - v) \cdot {\bf 1} = 0, |u - v|_1 \leq c \}| = \Theta(c^{d-1})$. $\endgroup$
    – Peter Taylor
    Commented Dec 22, 2022 at 22:05
  • $\begingroup$ Thanks a lot for this idea @PeterTaylor , I think that it should be sufficient in my case ! $\endgroup$
    – Ludwich
    Commented Dec 23, 2022 at 8:33

1 Answer 1

Reset to default
2
$\begingroup$

This is not the best upper bound, but for the second set, ($\ast$) tells us about the norm of $u$ and $v$ and $\sum_{i=1}^{d}|u_i-v_i|$ is the $L_1$ distance between $u$ and $v$ (Manhattan metric). Ignoring $\ast$ we get an upper bound by counting the lattice points in the ball of radius $c$. Now considering $\ast$, we intersect this ball with the surface of a radius $k$ sphere (in this metric), this sharpens our bound. Hope this help you having a linear programming perspective.

Improve this answer
$\endgroup$

You must log in to answer this question.

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