\documentclass[10pt]{article} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} \usepackage{lmodern} \usepackage{amsmath,amssymb,amsthm,mathtools} \usepackage{booktabs} \usepackage{microtype} \usepackage[margin=1in]{geometry} \usepackage[hidelinks]{hyperref} \hypersetup{pdftitle={The planar data-selection constants F(2,n)=2n/(2n-1), including F(2,3)=6/5 and F(2,2)=4/3},pdfauthor={Samuil Petkov}} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem*{definition*}{Definition} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\mathbb{E}} \newcommand{\supp}{\operatorname{supp}} \newcommand{\diag}{\operatorname{diag}} \newcommand{\norm}[1]{\lVert #1\rVert} \newcommand{\ip}[2]{\langle #1,#2\rangle} \newcommand{\T}{\mathsf T} \title{The planar data-selection constants $F(2,n)=2n/(2n-1)$,\\ including $F(2,3)=6/5$ and $F(2,2)=4/3$} \author{Samuil Petkov\\[2pt] \small Department of Physics, \'Ecole normale sup\'erieure, Universit\'e PSL, Paris, France\\ \small \texttt{samuil.petkov@phys.ens.psl.eu}} \date{} \begin{document} \maketitle \begin{abstract} For a finite multiset $D\subset\R^2$ let $L_D^*$ be the least mean squared distance from a point to $D$, and let $L_D^*(n)$ be the least such loss attained at the average of $n$ points selected from $D$ with repetition. Hanneke, Moran, Shlimovich and Yehudayoff asked for $F(d,n)=\sup_D L_D^*(n)/L_D^*$. We prove $F(2,n)=2n/(2n-1)$ for every $n\ge2$: every finite planar multiset satisfies $L_D^*(n)\le\frac{2n}{2n-1}L_D^*$, with equality for $2n-1$ copies of $(0,0)$ and one copy of $(1,0)$. In particular $F(2,3)=6/5$, and $F(2,2)=4/3$ receives a short proof. The proof reduces to three support points by a mean-preserving Carath\'eodory argument and then exhibits an explicit random selection of $n$ support points, supported on one small triangle of the selection grid, whose second moment about the population weights is dominated by $\frac1{2n-1}$ times the categorical covariance. For $n\in\{2,3\}$ we also give random selections attaining this second moment exactly. \end{abstract} \noindent\textbf{Mathematics Subject Classification (2020).} Primary 68Q32; Secondary 62H12, 52A40, 60E15. \noindent\textbf{Keywords.} data selection, mean estimation, worst-case approximation ratio, Carath\'eodory theorem, selection certificates, COLT open problem. \section{Problem and context} Let $D=\{z_1,\dots,z_N\}\subset\R^d$ be a finite multiset and \[ L_D(h)=\frac1N\sum_{r=1}^N\norm{h-z_r}^2,\qquad L_D^*=\min_{h\in\R^d}L_D(h),\qquad L_D^*(n)=\min_{x_1,\dots,x_n\in D}L_D\Bigl(\frac1n\sum_{k=1}^n x_k\Bigr). \] The selected points $x_1,\dots,x_n$ range over $D$ independently, so a point may be selected more often than it occurs in $D$; equivalently, $(x_1,\dots,x_n)$ is any sequence in $\supp(D)$, the set of distinct points of $D$ (this is the convention of \cite[\S7.2]{HMSYerm}). Question~1 of the COLT 2025 open-problem note \cite{HMSYopen} asks for \[ F(d,n)=\sup_{D\subset\R^d}\frac{L_D^*(n)}{L_D^*}, \] where we use the conventions $0/0=1$ and that $D$ ranges over nonempty finite multisets. The note summarizes the known values as follows; all entries except $d=n=2$ are due to \cite{HMSYerm}, and the authors describe their derivation of the $d=n=2$ entry as ``somewhat tedious and computational'' \cite[\S2]{HMSYopen}. \begin{center} \begin{tabular}{c|ccccc} \toprule $d\backslash n$ & $1$ & $2$ & $3$ & $n$ & $n\to\infty$\\ \midrule $1$ & $2$ & $4/3$ & $6/5$ & $2n/(2n-1)$ & $1$\\ $2$ & $2$ & $4/3$ & $?$ & $?$ & $1$\\ $3$ & $2$ & $?$ & $?$ & $?$ & $1$\\ $d\to\infty$ & $2$ & $3/2$ & $4/3$ & $(n+1)/n$ & undefined\\ \bottomrule \end{tabular} \end{center} For every $d$ and $n$ one has $2n/(2n-1)\le F(d,n)\le(n+1)/n$ \cite[\S7.5]{HMSYerm}; the lower bound comes from the one-dimensional example recalled in Proposition~\ref{prop:lower}. \begin{theorem}\label{thm:all} Let $n\ge2$. Every finite multiset $D\subset\R^2$ satisfies $L_D^*(n)\le\frac{2n}{2n-1}L_D^*$, with equality for $2n-1$ copies of $(0,0)$ and one copy of $(1,0)$. Hence $F(2,n)=2n/(2n-1)$, and the supremum is attained. \end{theorem} Together with $F(2,1)=2$ from the table, Theorem~\ref{thm:all} determines the row $d=2$ of the table. Its cases $n=3$ and $n=2$ read as follows. \begin{theorem}\label{thm:main} Every finite multiset $D\subset\R^2$ satisfies $L_D^*(3)\le\frac65L_D^*$, with equality for five copies of $(0,0)$ and one copy of $(1,0)$. Hence $F(2,3)=6/5$, and the supremum is attained. \end{theorem} \begin{theorem}\label{thm:two} Every finite multiset $D\subset\R^2$ satisfies $L_D^*(2)\le\frac43L_D^*$, with equality for three copies of $(0,0)$ and one copy of $(1,0)$. Hence $F(2,2)=4/3$. \end{theorem} The value $F(2,2)=4/3$ is already stated in \cite{HMSYopen}; Theorem~\ref{thm:two} gives a short proof of it. Other questions from \cite{HMSYopen}, on weighted data selection for linear regression, are treated in \cite{ZhangRisk,ZhangVector}; those works do not concern the mean-estimation constants $F(d,n)$ studied here. For $n\in\{2,3\}$ we give, besides the general argument, certificates that are exact in the sense of \eqref{eq:cert} below. Throughout, $n\ge2$ and \[ r_n:=\frac1{2n-1}. \] \section{Reduction to three support points} Write a finite multiset as a probability law $P=\{(z_i,p_i)\}_{i=1}^m$ on its distinct points, $p_i=n_i/N$, and set \[ \mu(P)=\sum_ip_iz_i,\qquad V(P)=\sum_ip_i\norm{z_i-\mu(P)}^2,\qquad q_n(P)=\min_{x_1,\dots,x_n\in\supp P}\Bigl\lVert\frac1n\sum_{k=1}^nx_k-\mu(P)\Bigr\rVert^2 . \] These definitions make sense for any finitely supported law with real weights. Expanding $h-z_i=(h-\mu)-(z_i-\mu)$ and using $\sum_ip_i(z_i-\mu)=0$ gives \begin{equation}\label{eq:pyth} L_D(h)=V(P)+\norm{h-\mu(P)}^2\qquad(h\in\R^2). \end{equation} Hence $L_D^*=V(P)$, attained only at $h=\mu(P)$, and $L_D^*(n)=V(P)+q_n(P)$. If $V(P)=0$ then $D$ is a single repeated point and $L_D^*(n)=L_D^*=0$. If $V(P)>0$ then \begin{equation}\label{eq:target} \frac{L_D^*(n)}{L_D^*}\le1+r_n=\frac{2n}{2n-1} \quad\Longleftrightarrow\quad q_n(P)\le r_n\,V(P). \end{equation} \begin{lemma}[Mean-preserving support reduction]\label{lem:cara} Let $P$ be a finitely supported probability law on $\R^2$. There is a probability law $P'$ with $\supp P'\subseteq\supp P$, $|\supp P'|\le3$, $\mu(P')=\mu(P)$ and $V(P')\le V(P)$. Consequently $q_n(P)\le q_n(P')$ for every $n$. \end{lemma} \begin{proof} Let $z_1,\dots,z_m$ be the support of $P$ and $\mu=\mu(P)$. The set \[ \mathcal P=\Bigl\{a\in\R^m:\ a\ge0,\ \sum_ia_i=1,\ \sum_ia_iz_i=\mu\Bigr\} \] contains the weight vector $p$ of $P$ and is compact. The linear function $J(a)=\sum_ia_i\norm{z_i}^2$ therefore attains its minimum on $\mathcal P$; choose a minimizer $a^*$ with the fewest positive coordinates. Suppose $a^*$ had at least four positive coordinates. The corresponding columns $(1,z_i)\in\R^3$ are linearly dependent, so there is $u\ne0$ supported on $\{i:a_i^*>0\}$ with $\sum_iu_i=0$ and $\sum_iu_iz_i=0$. For small $t>0$ both $a^*\pm tu$ lie in $\mathcal P$, so minimality gives $\pm tJ(u)\ge0$, that is $J(u)=0$. Since $u\ne0$ and $\sum_iu_i=0$, $u$ has a negative coordinate; with $t_0=\min_{u_i<0}a_i^*/(-u_i)>0$, the vector $a^*+t_0u$ lies in $\mathcal P$, has $J(a^*+t_0u)=J(a^*)$, and has fewer positive coordinates than $a^*$, a contradiction. So the law $P'$ with weights $a^*$ has at most three support points, all in $\supp P$, and mean $\mu$. For every $a\in\mathcal P$, \[ \sum_ia_i\norm{z_i-\mu}^2=J(a)-2\Bigl\langle\sum_ia_iz_i,\mu\Bigr\rangle+\norm{\mu}^2=J(a)-\norm{\mu}^2, \] so $V(P')=J(a^*)-\norm\mu^2\le J(p)-\norm\mu^2=V(P)$. Finally, every selection legal for $P'$ is legal for $P$ and both laws have the same mean, so $q_n(P)\le q_n(P')$. \end{proof} By Lemma~\ref{lem:cara}, if $q_n(P')\le r_nV(P')$ holds for all laws with at most three support points, then for every finitely supported $P$ \begin{equation}\label{eq:chain} q_n(P)\le q_n(P')\le r_nV(P')\le r_nV(P). \end{equation} This reduction is of Carath\'eodory type; compare the use of Carath\'eodory's theorem for convex functions in \cite[\S7.1]{HMSYerm}. \section{Grid certificates} Let $P$ have support contained in three labelled points $v_1,v_2,v_3$ with weights $p=(p_1,p_2,p_3)$, $p_i\ge0$, $\sum_ip_i=1$; labels with $p_i=0$ are padding and may not be selected. Put $w_i=v_i-\mu(P)$, so that $\sum_ip_iw_i=0$ and $V(P)=\sum_ip_i\norm{w_i}^2$. A selection of $n$ labels with multiplicities $k=(k_1,k_2,k_3)$, $\sum_ik_i=n$, is encoded by the grid point $s=k/n$ in \[ G_n=\Bigl\{\tfrac1n k:\ k\in\mathbb Z_{\ge0}^3,\ k_1+k_2+k_3=n\Bigr\}, \] and its selected mean, centred at $\mu(P)$, is $\sum_is_iw_i=\sum_i(s_i-p_i)w_i$. Let $C_p=\diag(p)-pp^\T$ be the covariance matrix of a categorical draw with probabilities $p$, and write $A\preceq B$ if $B-A$ is positive semidefinite. \begin{definition*} A \emph{certificate} for $(n,p)$ is a probability distribution $\lambda$ on $G_n$ such that $\lambda_s=0$ whenever $s_i>0$ for some $i$ with $p_i=0$, and \begin{equation}\label{eq:certle} M_\lambda:=\sum_{s\in G_n}\lambda_s\,(s-p)(s-p)^\T\preceq r_n\,C_p . \end{equation} It is \emph{exact} if \begin{equation}\label{eq:cert} M_\lambda=r_n\,C_p . \end{equation} \end{definition*} \begin{lemma}[Extraction]\label{lem:extract} If a certificate exists for $(n,p)$, then $q_n(P)\le r_nV(P)$. \end{lemma} \begin{proof} Let $S$ be a random grid point with law $\lambda$ and $Y=\sum_iS_iw_i=\sum_i(S_i-p_i)w_i$. Let $\Gamma$ be the Gram matrix $\Gamma_{ij}=\ip{w_i}{w_j}$, which is positive semidefinite. Then \[ \E\norm Y^2=\sum_{i,j}\E[(S_i-p_i)(S_j-p_j)]\,\Gamma_{ij}=\operatorname{tr}(M_\lambda\Gamma),\qquad \operatorname{tr}(C_p\Gamma)=\sum_ip_i\norm{w_i}^2-\Bigl\lVert\sum_ip_iw_i\Bigr\rVert^2=V(P). \] The trace of a product of two positive semidefinite matrices is nonnegative, so \eqref{eq:certle} gives $\operatorname{tr}\bigl((r_nC_p-M_\lambda)\Gamma\bigr)\ge0$, that is $\E\norm Y^2\le r_nV(P)$, with equality for exact certificates. Every $s$ with $\lambda_s>0$ encodes a legal selection of $n$ support points, and $\E\norm Y^2$ is a $\lambda$-average of their squared errors. Hence some legal selection has squared error at most $r_nV(P)$. \end{proof} No condition $\E S=p$ is required. The following identity reduces \eqref{eq:cert} to first and second moments. \begin{lemma}\label{lem:moments} Let $\lambda$ be a probability distribution on $G_n$, $m=\E S$ and $Q=\E[SS^\T]$. If for some $c\in\R^3$ \[ m=\tfrac{1+r_n}{2}\,p+c\qquad\text{and}\qquad Q=r_n\diag(p)+cp^\T+pc^\T, \] then $\lambda$ satisfies \eqref{eq:cert}. \end{lemma} \begin{proof} $\E[(S-p)(S-p)^\T]=Q-mp^\T-pm^\T+pp^\T=r_n\diag(p)+cp^\T+pc^\T-(1+r_n)pp^\T-cp^\T-pc^\T+pp^\T=r_nC_p$. \end{proof} Write $e_1,e_2,e_3$ for the vertices of $G_n$ and assume, after relabelling, $p_1\ge p_2\ge p_3$; a simultaneous permutation of labels maps $G_n$ to itself and conjugates both sides of \eqref{eq:cert} by the same permutation matrix. \begin{lemma}[Corner certificate, any $n\ge2$]\label{lem:corner} Let $\kappa=n^2/(2n-1)$ and suppose $p_1\ge\bigl(\frac{n-1}{n}\bigr)^2$. The weights \[ \lambda\bigl(e_1+\tfrac1n(e_2-e_1)\bigr)=\kappa p_2,\qquad \lambda\bigl(e_1+\tfrac1n(e_3-e_1)\bigr)=\kappa p_3,\qquad \lambda(e_1)=1-\kappa(p_2+p_3) \] form an exact certificate for $(n,p)$. \end{lemma} \begin{proof} The first two weights are nonnegative, and $1-\kappa(1-p_1)=\bigl(n^2p_1-(n-1)^2\bigr)/(2n-1)\ge0$ by hypothesis; the weights sum to one. A label with $p_i=0$ ($i=2,3$) receives weight zero. Using $\kappa/n=n/(2n-1)=(1+r_n)/2$ and $\kappa/n^2=r_n$, \[ m_1=1-\tfrac{\kappa}{n}(p_2+p_3)=\tfrac{n p_1+n-1}{2n-1},\qquad m_2=\tfrac{n}{2n-1}p_2,\qquad m_3=\tfrac{n}{2n-1}p_3, \] so $m=\frac{1+r_n}2p+c$ with $c=\frac{n-1}{2n-1}e_1$. For the second moments, \[ Q_{22}=\tfrac{\kappa}{n^2}p_2=r_np_2,\quad Q_{33}=r_np_3,\quad Q_{23}=0,\quad Q_{12}=\tfrac{\kappa(n-1)}{n^2}p_2=\tfrac{n-1}{2n-1}p_2,\quad Q_{13}=\tfrac{n-1}{2n-1}p_3, \] \[ Q_{11}=1-\kappa(p_2+p_3)\Bigl(1-\bigl(\tfrac{n-1}{n}\bigr)^2\Bigr)=1-(1-p_1)=p_1 . \] These are exactly the entries of $r_n\diag(p)+cp^\T+pc^\T=r_n\diag(p)+\frac{n-1}{2n-1}(e_1p^\T+pe_1^\T)$; for instance its $(1,1)$ entry is $r_np_1+\frac{2(n-1)}{2n-1}p_1=p_1$ and its $(2,3)$ entry is $0$. Lemma~\ref{lem:moments} applies. \end{proof} \begin{lemma}[Central certificate, $n=3$]\label{lem:central} Let $n=3$, $p_1\ge p_2\ge p_3$ and $p_2\ge\frac16$. Writing $s_{abc}=\frac13(a,b,c)$, the weights \[ \lambda(s_{111})=\tfrac95p_3,\qquad \lambda(s_{120})=\tfrac95p_2-\tfrac3{10},\qquad \lambda(s_{210})=\tfrac95p_1-\tfrac35,\qquad \lambda(s_{300})=\tfrac1{10} \] form an exact certificate for $(3,p)$. \end{lemma} \begin{proof} Nonnegativity: $p_3\ge0$; $p_2\ge\frac16$; and $p_1\ge\frac13$ by sortedness. The sum is $\frac95-\frac3{10}-\frac35+\frac1{10}=1$. Only $s_{111}$ uses label $3$, and its weight vanishes if $p_3=0$; labels $1,2$ have positive weight since $p_1\ge p_2\ge\frac16$. The first moments are \begin{gather*} m_1=\tfrac13\lambda_{111}+\tfrac13\lambda_{120}+\tfrac23\lambda_{210}+\lambda_{300}=\tfrac{3p_1+1}5,\qquad m_2=\tfrac13\lambda_{111}+\tfrac23\lambda_{120}+\tfrac13\lambda_{210}=\tfrac{3p_2+1}5,\\ m_3=\tfrac13\lambda_{111}=\tfrac35p_3, \end{gather*} so $m=\frac35p+c$ with $c=\frac15(1,1,0)$, and $\frac35=\frac{1+r_3}2$. The second moments are \begin{gather*} Q_{11}=\tfrac19\lambda_{111}+\tfrac19\lambda_{120}+\tfrac49\lambda_{210}+\lambda_{300}=\tfrac35p_1,\qquad Q_{22}=\tfrac19\lambda_{111}+\tfrac49\lambda_{120}+\tfrac19\lambda_{210}=\tfrac35p_2,\\ Q_{12}=\tfrac19\lambda_{111}+\tfrac29\lambda_{120}+\tfrac29\lambda_{210}=\tfrac{p_1+p_2}5,\qquad Q_{13}=Q_{23}=Q_{33}=\tfrac19\lambda_{111}=\tfrac15p_3 . \end{gather*} With $c=\frac15(1,1,0)$ and $r_3=\frac15$, the matrix $r_3\diag(p)+cp^\T+pc^\T$ has entries $(1,1)\colon\frac{3p_1}5$, $(2,2)\colon\frac{3p_2}5$, $(3,3)\colon\frac{p_3}5$, $(1,2)\colon\frac{p_1+p_2}5$, $(1,3)\colon\frac{p_3}5$, $(2,3)\colon\frac{p_3}5$, which agree with $Q$. Lemma~\ref{lem:moments} applies. \end{proof} \begin{proposition}\label{prop:cover} For $n\in\{2,3\}$ an exact certificate exists for every $p$ in the simplex. \end{proposition} \begin{proof} Sort $p_1\ge p_2\ge p_3$. For $n=2$ the hypothesis of Lemma~\ref{lem:corner} is $p_1\ge\frac14$, which holds because $p_1\ge\frac13$. For $n=3$: if $p_2\ge\frac16$ use Lemma~\ref{lem:central}; otherwise $p_3\le p_2<\frac16$, so $p_1>\frac23\ge\frac49=\bigl(\frac23\bigr)^2$ and Lemma~\ref{lem:corner} applies. \end{proof} For $n=2$ the certificate of Lemma~\ref{lem:corner} is explicit: weight $\frac{4p_1-1}3$ on $e_1$ and $\frac43p_2$, $\frac43p_3$ on the midpoints $\frac12(e_1+e_2)$, $\frac12(e_1+e_3)$. For $n=3$ and $p_2<\frac16$ it is $\frac95p_2$ on $s_{210}$, $\frac95p_3$ on $s_{201}$ and $\frac{9p_1-4}5$ on $s_{300}$. \section{Certificates for every \texorpdfstring{$n$}{n}} For $k\in\mathbb Z_{\ge0}^3$ with $k_1+k_2+k_3=n-1$, the three grid points $(k+e_i)/n$, $i=1,2,3$, are the vertices of a small triangle of $G_n$ that is a translate of $\frac1n\{e_1,e_2,e_3\}$. \begin{lemma}[Triangle certificate, any $n\ge2$]\label{lem:triangle} Let $k\in\mathbb Z_{\ge0}^3$ with $k_1+k_2+k_3=n-1$ and $(n-1)k_i\le n^2p_i$ for $i=1,2,3$. Put \[ t_i=\tfrac1n(k+e_i)\in G_n,\qquad \beta_i=\frac{n^2p_i-(n-1)k_i}{2n-1}\qquad(i=1,2,3), \] and let $\lambda=\sum_i\beta_i\delta_{t_i}$. Then $\lambda$ is a certificate for $(n,p)$; more precisely \begin{equation}\label{eq:triangle} M_\lambda=\sum_{i=1}^3\beta_i(t_i-p)(t_i-p)^\T=r_nC_p-\frac{r_n}{n^2}R_k,\qquad R_k:=(n-1)\diag(k)-kk^\T\succeq0 . \end{equation} \end{lemma} \begin{proof} The weights are nonnegative by hypothesis and sum to $\bigl(n^2-(n-1)^2\bigr)/(2n-1)=1$. If $p_i=0$, the hypothesis forces $k_i=0$; then $\beta_i=0$, and $t_j$ has $i$-th coordinate $0$ for $j\ne i$, so the padding condition holds. Put $u=k/n$ and $a=u-p$, so that $t_i-p=a+\frac1ne_i$. Since $\sum_i\beta_i=1$, $\sum_i\beta_ie_i=\beta$ and $\sum_i\beta_ie_ie_i^\T=\diag(\beta)$, \[ M_\lambda=aa^\T+\tfrac1n\bigl(a\beta^\T+\beta a^\T\bigr)+\tfrac1{n^2}\diag(\beta). \] From $\beta=\bigl(n^2p-n(n-1)u\bigr)/(2n-1)$ and $p=u-a$ we get $\frac1n\beta=r_n\bigl(np-(n-1)u\bigr)=r_n(u-na)$ and $\frac1{n^2}\beta=r_np-r_n\frac{n-1}{n}u$. Hence, using $1-2nr_n=-r_n$, \[ M_\lambda=r_n\Bigl(\diag(p)-aa^\T+au^\T+ua^\T-\tfrac{n-1}{n}\diag(u)\Bigr). \] On the other hand $pp^\T=(u-a)(u-a)^\T=uu^\T-au^\T-ua^\T+aa^\T$, so \[ r_nC_p=r_n\bigl(\diag(p)-uu^\T+au^\T+ua^\T-aa^\T\bigr). \] Subtracting, $M_\lambda-r_nC_p=r_n\bigl(uu^\T-\frac{n-1}n\diag(u)\bigr)=-\frac{r_n}{n^2}R_k$. Finally, for $x\in\R^3$, $x^\T R_kx=\bigl(\sum_ik_i\bigr)\bigl(\sum_ik_ix_i^2\bigr)-\bigl(\sum_ik_ix_i\bigr)^2\ge0$ by the Cauchy--Schwarz inequality, so $R_k\succeq0$ and \eqref{eq:certle} holds. \end{proof} For $k=(n-1)e_1$ one has $R_k=0$, and Lemma~\ref{lem:triangle} is exactly the corner certificate of Lemma~\ref{lem:corner}; the same holds for $k=(n-1)e_2$ or $(n-1)e_3$ after relabelling. If two coordinates of $k$ are positive, then $R_k\ne0$ and the certificate is not exact. \begin{lemma}\label{lem:count} For every $n\ge2$ and every $p$ in the simplex there is $k\in\mathbb Z_{\ge0}^3$ with $k_1+k_2+k_3=n-1$ and $(n-1)k_i\le n^2p_i$ for $i=1,2,3$. \end{lemma} \begin{proof} Put $x_i=n^2p_i/(n-1)$, so $\sum_ix_i=\frac{n^2}{n-1}=n+1+\frac1{n-1}$. Since $\lfloor x_i\rfloor>x_i-1$, \[ \sum_{i=1}^3\lfloor x_i\rfloor>\sum_ix_i-3=n-2+\tfrac1{n-1}>n-2 , \] and the left side is an integer, so it is at least $n-1$. Choose integers $0\le k_i\le\lfloor x_i\rfloor$ with $k_1+k_2+k_3=n-1$. \end{proof} \begin{proposition}\label{prop:all} For every $n\ge2$ a certificate exists for every $p$ in the simplex. \end{proposition} \begin{proof} Combine Lemmas~\ref{lem:count} and~\ref{lem:triangle}. \end{proof} \section{Proofs of the theorems} \begin{proposition}[Extremal examples {\cite{HMSYerm}}]\label{prop:lower} Let $D_n$ consist of $2n-1$ copies of $(0,0)$ and one copy of $(1,0)$. Then $L_{D_n}^*(n)/L_{D_n}^*=2n/(2n-1)$. \end{proposition} \begin{proof} With $\theta=\frac1{2n}$, the mean is $(\theta,0)$ and $L^*_{D_n}=V=\theta(1-\theta)=\frac{2n-1}{4n^2}$. A selection containing $j$ copies of $(1,0)$ has mean $(j/n,0)$, at squared distance $(j/n-\theta)^2$ from the mean; the minimum, at $j\in\{0,1\}$, is $\theta^2=\frac1{4n^2}=r_nV$. By \eqref{eq:pyth}, $L^*_{D_n}(n)=(1+r_n)V$. \end{proof} For $n=3$ this is five copies of $(0,0)$ and one copy of $(1,0)$: mean $(\frac16,0)$, $V=\frac5{36}$, selected means $(j/3,0)$ at squared distances $\frac1{36},\frac1{36},\frac14,\frac{25}{36}$, so $L^*_D(3)=\frac16=\frac65\cdot\frac5{36}$. For $n=2$ it is three copies of $(0,0)$ and one copy of $(1,0)$, with $V=\frac3{16}$ and $q_2=\frac1{16}$. \begin{proof}[Proof of Theorems~\ref{thm:all}, \ref{thm:main} and~\ref{thm:two}] Let $n\ge2$ and let $D\subset\R^2$ be a finite multiset with law $P$. If $V(P)=0$ both losses vanish. Otherwise, Lemma~\ref{lem:cara} gives $P'$ with at most three support points, all in $\supp D$, the same mean and $V(P')\le V(P)$. Label the support of $P'$ as $v_1,v_2,v_3$, padding with zero-weight labels if necessary. Proposition~\ref{prop:all} (or, for $n\in\{2,3\}$, Proposition~\ref{prop:cover}) and Lemma~\ref{lem:extract} give $q_n(P')\le r_nV(P')$, and \eqref{eq:chain} gives $q_n(P)\le r_nV(P)$. By \eqref{eq:pyth} and \eqref{eq:target}, $L_D^*(n)\le\frac{2n}{2n-1}L_D^*$, which is $\frac65L_D^*$ for $n=3$ and $\frac43L_D^*$ for $n=2$. Proposition~\ref{prop:lower} shows that equality is attained. \end{proof} \begin{remark} Equality in Theorem~\ref{thm:main} is not confined to collinear data. Take four copies of $a=(1,-1)$ and one copy each of $b=(1,5)$ and $c=(-5,-1)$. The mean is $0$ and $V=\frac16(4\cdot2+26+26)=10$. A selection with multiplicities $k_1+k_2+k_3=3$ has mean $\frac13(k_1a+k_2b+k_3c)=(1-2k_3,\,2k_2-1)$, whose coordinates are odd integers; its squared norm is at least $2$, with equality for instance for $k=(3,0,0)$. Thus $q_3=2=V/5$. \end{remark} \begin{remark}[Higher dimensions] Lemmas~\ref{lem:extract} and~\ref{lem:triangle} extend verbatim to $d+1$ labels, and in $\R^d$ the argument of Lemma~\ref{lem:cara} reduces to $d+1$ support points. The counting in Lemma~\ref{lem:count} then only gives $\sum_i\lfloor x_i\rfloor>n-d+\frac1{n-1}$, which is not enough for $d\ge3$. We make no claim about $F(d,n)$ for $d\ge3$. \end{remark} \section*{AI assistance disclosure} OpenAI GPT-5.6 Sol, accessed through ChatGPT and Codex, was used to develop and audit the original proof of $F(2,3)=6/5$ and its exact verification, and for drafting. Anthropic Claude Opus 5.5, used through Claude Code, condensed the manuscript, found the triangle certificate (Lemma~\ref{lem:triangle}, Lemma~\ref{lem:count}) that gives $F(2,n)=2n/(2n-1)$ for every $n$ (Theorem~\ref{thm:all}), and checked the certificate identities with exact symbolic and rational computation. The author reviewed and takes responsibility for every statement and proof. AI systems are not authors of this work, and the work has not been peer reviewed. \begin{thebibliography}{9} \bibitem{HMSYopen} S.~Hanneke, S.~Moran, A.~Shlimovich, and A.~Yehudayoff, \emph{Open problem: Data selection for regression tasks}, Proceedings of the Thirty Eighth Conference on Learning Theory, Proc.\ Mach.\ Learn.\ Res.\ \textbf{291} (2025), 6225--6229. \url{https://proceedings.mlr.press/v291/hanneke25e.html} \bibitem{HMSYerm} S.~Hanneke, S.~Moran, A.~Shlimovich, and A.~Yehudayoff, \emph{Data selection for ERMs}, Proceedings of the Thirty Eighth Conference on Learning Theory, Proc.\ Mach.\ Learn.\ Res.\ \textbf{291} (2025), 2634--2665; section numbers refer to arXiv:2504.14572v2. \url{https://proceedings.mlr.press/v291/hanneke25a.html} \bibitem{ZhangRisk} G.~Zhang, \emph{Exact risk ratios for weighted data selection in linear regression}, preprint (2026), arXiv:2608.28007. \bibitem{ZhangVector} G.~Zhang, \emph{Exact recovery thresholds for weighted data selection in vector-valued linear regression}, preprint (2026), arXiv:2608.30254. \end{thebibliography} \end{document}