# Sum of k smallest values of affine functions

Assume we have a fixed number of $n$ one-dimensional affine functions of the form $f_i(x) = a_i x + b_i$ for $i \in N = \{1,\ldots,n\}$.

Consider some fixed value $k \in \{0,\ldots,n\}$. Let $S_k : \mathbb{R} \mapsto 2^N$ (power set) denote a function mapping some value $x \in \mathbb{R}$ to the set of indices of the $k$ smallest functions at $x$, so for all $x \in \mathbb{R}$, it holds that $|S_k(x)| = k$ and $f_i(x) \leq f_j(x)$ if $i \in S_k(x)$ and $j \notin S_k(x)$.

The question is: If we hold $f_1,\dots,f_n,k$ fixed and allow $x$ to vary, how many different sets can $S_k$ map to? In other words, which cardinality can the image of $S_k$ have?

For $k=0$ or $k=n$, there is only one possible set for all $x$ (either $\emptyset$ or $N$). Similarly, for $k=1$ or $k=n-1$, there are $n$ different sets each (since this is equal to the maximum or minimum element, which can change $n$ times while x increases).

But is there a general formula for arbitrary values of $k$? It seems that the maximum is attained at $k = \frac{n}{2}$.

Note that an upper bound is given by $O(n^2)$ since this is the maximum number of intersection points of the involved functions, which, thus, bounds the number of orderings. However, I think this bound is too rough. In computational experiments I have never seen a value of $2n$ or more.

• Thanks for the remark, I tried to formulate the question and the assumptions in a clearer way. In a broad sense, the problem is motivated by a variant of the Knapsack problem, but I fear I cannot go much into detail here. – user1742364 Feb 3 '17 at 19:08
• One thought on how you could explore this further yourself: fix $k=2$, and compute the number for small values of $n$ (e.g., $n=1,2,3,\dots,10$) by writing a program to search all possibilities, and show in the question what numbers you've come up with (and check OEIS). – D.W. Feb 3 '17 at 21:32
• If we only consider the case of $f_i$'s in general position (no two are parallel, and no three intersect), then there is an alternative formulation in terms of permutations. Starting with the inverse permutation $n\;n-1\;\cdots\;1$, sort it by repeatedly transposing adjacent elements which are in the wrong order. Consider the first $k$ elements throughout this process. How many different sets can you see? – Yuval Filmus Mar 9 '17 at 11:48
• @D.W. Brute force is only feasible up to $n=6$ or $n=7$, see oeis.org/A005118. – Yuval Filmus Mar 9 '17 at 11:57

I recently found out that my problem is known as the k-th level problem, which itself is equivalent to the k-set problem in the dual plane. Since almost 50 years, it is an open problem how many sets there are exactly. At present, the best upper bound is given by $O(n k ^{1/3})$: https://en.wikipedia.org/wiki/K-set_(geometry)