4
$\begingroup$

Let $\|\vec{x}\|_1$ represent the sum of the components (the L1 norm) of $\vec{x}$. Define $$A_n = \{\vec{x}:\vec{x}\in\mathbb{\mathbb{N}}^n, x_i\ne x_j \textrm{ for } i\ne j,\|\vec{x}\|_1\notin B(\vec{x})\},$$ where $$B(\vec{x}) = \left\{\sum_{i=1}^{n} a_ix_i: (a_1,\ldots,a_n)\in\mathbb{Z}^{n}_{\ge 0}-(1, 1, \ldots, 1)\right\}.$$ Furthermore, let $$C_n=\{\vec{c}\in A_n:\|\vec{c}\|_1=\min_{A_n} \|\vec{a}\|_1\}.$$

Can we determine $C_n$?

Forgive me if my notation is off, this seems to be a bit of a complicated problem.

To explain in words, $A_n$ is the set of all vectors $\vec{x}$ with $n$ components where each component is a distinct positive integer satisfying the property that the sum of the components of each $\vec{x}$ cannot be formed by summing the components of any combination (with repetition) of the components of $\vec{x}$, excluding $\vec{x}$ itself, of course. Hence, $C_n$ is set of vectors in $A_n$ having the smallest L1 norm.

Through a brute force approach in Python, I found for $n=1, 2, 3, 4$:

$C_1 = \{(1)\}$

$C_2 = \{(2, 3)\}$

$C_3 = \{(4, 6, 7)\}$

$C_4 = \{(8, 12, 14, 15)\}$

And I think the pattern that emerges is clear. But can you mathematically prove that this pattern continues?

Here's the Python code, for reference: https://www.onlinegdb.com/Sk9-TaQ8Q

$\endgroup$
1
$\begingroup$

I do not have a full answer, but at the very least one can prove that the vector $\vec{v}_n\in \mathbb{N}^{n}$ with components $v_{i,n} = 2^{n}-2^{n - i}$ for $i=1, \ldots, n$ satisfies the condition. This is actually quite easy by induction. Let us consider $\vec{v}_{n+1}$ in $\mathbb{N}^{n+1}$ and suppose that $$\sum_{i=1}^{n+1} v_{i,n+1} = (n+1)\cdot 2^{n+1} - \sum_{i=1}^{n+1} 2^{n+1-i} = n\cdot2^{n+1} + 1 = \sum_{i=1}^{n+1} a_i v_{i,n+1}$$ for some integers $a_i\ge 0.$

Note that $\sum_{i=1}^{n+1} a_i \ge n+1,$ since otherwise the right-hand side of the above equation is at most $n\cdot v_{n+1} = n\cdot(2^{n+1}-1).$ Now subtract $2^{n}$ from each term on the LHS and from $(n+1)$ terms on the RHS to reduce to the case with $n$ components. If the RHS has extra terms, you can simply write them as $2^{n} + (v_{i,n+1} - 2^{n}) = 2\cdot v_{1,n} + v_{i-1, n}.$ In the case $i=1, v_{0,n} = 0.$ In any case, the induction hypothesis implies $a_i = 1$ for all $i.$

I want to add that for any such vector, the smallest component must be at least $2^{n-1}.$ This is because if any two subsets of the remaining $n-1$ component are congruent modulo $v_1,$ then the vector fails. Hence $v_1\ge 2^{n-1}.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.