3
$\begingroup$

if I want to make a subset of numbers for which sums of pairs involve all even numbers what is the subset with the smallest density?

for example {1 , 3 , 5} can pair to get 2 :1+1 , 4 :1+3 , 6 :3+3, 8: 5+3, 10 :5+5 so all even numbers until 10 can be achieved with a set of 3 numbers.

I made a java program that gets the smallest possible set by trying all possibilities. It reached 42 then (out of memory error) but the size of the set seemed to be approximately :

Size =The Largest Even Number/ log2(The Largest Even Number)

for 42 it is 7 , for 22 it is 5. Does this hold for larger numbers? And is there a theorem for that?

$\endgroup$
2
  • $\begingroup$ oeis.org/A066063 $\endgroup$
    – RobPratt
    Aug 7 at 18:42
  • $\begingroup$ When you format your equations in a good mathematical style, it's easier to see whether you mean $(\log 2)\times(\text{largest even number})$ or $\log_2(\text{largest even number}).$ Although we can see from the answer below that even the second formula is not accurate for larger sums. $\endgroup$
    – David K
    Aug 7 at 19:16

1 Answer 1

4
$\begingroup$

For fixed $n$, you can solve the problem via integer linear programming as follows. For $i\in\{1,\dots,n\}$, let binary decision variable $x_i$ indicate whether element $i$ is selected. The problem is to minimize $\sum_i x_i$ subject to $$\sum_{i\le k-i} x_i x_{k-i} \ge 1 \quad \text{for $k\in\{2,4,\dots,n\}$} \tag1\label1.$$ You can linearize these quadratic constraints \eqref{1} by introducing (nonnegative or binary) variables $y_{ij}$ to represent the products $x_i x_j$, together with linear constraints \begin{align} \sum_{i\le k-i} y_{i,k-i} &\ge 1 &&\text{for $k\in\{2,4,\dots,n\}$} \tag2\label2 \\ y_{ij} &\le x_i && \text{for $1\le i \le j \le n$} \tag3\label3 \\ y_{ij} &\le x_j && \text{for $1\le i \le j \le n$} \tag4\label4 \end{align}

The optimal objective values for even $n$ up to $100$ are: \begin{matrix} n & \sum_i x_i \\ \hline 2 & 1 \\ 4 & 2 \\ 6 & 2 \\ 8 & 3 \\ 10 & 3 \\ 12 & 4 \\ 14 & 4 \\ 16 & 4 \\ 18 & 4 \\ 20 & 5 \\ 22 & 5 \\ 24 & 5 \\ 26 & 5 \\ 28 & 6 \\ 30 & 6 \\ 32 & 6 \\ 34 & 6 \\ 36 & 7 \\ 38 & 7 \\ 40 & 7 \\ 42 & 7 \\ 44 & 8 \\ 46 & 8 \\ 48 & 8 \\ 50 & 8 \\ 52 & 8 \\ 54 & 8 \\ 56 & 9 \\ 58 & 9 \\ 60 & 9 \\ 62 & 9 \\ 64 & 9 \\ 66 & 9 \\ 68 & 10 \\ 70 & 10 \\ 72 & 10 \\ 74 & 10 \\ 76 & 10 \\ 78 & 10 \\ 80 & 10 \\ 82 & 10 \\ 84 & 11 \\ 86 & 11 \\ 88 & 11 \\ 90 & 11 \\ 92 & 11 \\ 94 & 11 \\ 96 & 12 \\ 98 & 12 \\ 100 & 12 \end{matrix}

$\endgroup$
8
  • $\begingroup$ good. Note that the smallest set $S$ of non-negative integers for which $S+S$ contains all even naturals has density zero. Indeed, if we let $S$ be the set of all integers $n = x^2 + y^2$ where $x,y$ are integers, in fact $S+S$ contains all natural numbers. $\endgroup$
    – Will Jagy
    Aug 7 at 18:06
  • $\begingroup$ Indeed, the same is true when $S$ equals the set of primes ... conjecturally! $\endgroup$ Aug 7 at 18:51
  • $\begingroup$ @GregMartin is there any set $S$ that gives all evens as pair sums and has density similar to the primes? i. e. up to large positive $n,$ the count of $S$ elements is about $\frac{x}{\log x}$ $\endgroup$
    – Will Jagy
    Aug 7 at 19:30
  • 1
    $\begingroup$ Yes: it's known that most even numbers can be written as the sum of two primes, so we could just insert $n-3$ for every exceptional even number $n$ without changing the density. That being said, the smallest such $S$ has counting function asymptotic to a constant times $\sqrt x$. I believe a reference to such a construction is: J. W. S. Cassels, Uber Basen der natürlichen Zahlenreihe, Abhandlungen Math. Seminar Univ. Hamburg 21 (1975), 247–257. $\endgroup$ Aug 7 at 20:03
  • $\begingroup$ An easy $x^{2/3}$ construction is to take all integers whose base-$8$ representation only has the digits $0, 1, 2, 5$. For this approach, it's enough to check that every base-$8$ digit can be decomposed: $0=0+0, 1=1+0, 2=2+0, 3=2+1, 4=2+2,5=5+0,6=5+1,7=5+2$. Then apply this to each digit: for example, $2022$ is $3722_8$, so it is the sum of $2522_8$ and $1200_8$. $\endgroup$ Aug 8 at 1:37

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.