3
$\begingroup$

Suppose $X$ is a subset of $\{1, \cdots, n\}$ such that the equation $ax_i+bx_j=cx_k+dx_{\ell}$ where $a+b=c+d,$ $a,b,c,d \in \mathbb{N}$ and $x_i, x_j, x_k, x_{\ell} \in X,$ has only trivial solution. A solution is trivial if $x_i=x_j=x_{k}=x_{\ell}.$

What can we say about the size of $X?$ Is this possible that $|X|\geq n^{1-o(1)}$?

I think the answer is related to Sidon Sets, but I could not find any references. Any help is greatly appreciated.

Improve this question
$\endgroup$
7
  • $\begingroup$ are $a,b,c,d$ fixed? Else there are solutions like $a=c,b=d$, $x_i=x_k$, $x_j=x_l$. $\endgroup$
    – Fedor Petrov
    Commented Oct 7, 2018 at 19:53
  • $\begingroup$ also maybe you need the reverse inequality for $|X|$? $\endgroup$
    – Fedor Petrov
    Commented Oct 7, 2018 at 20:01
  • $\begingroup$ Then "is it true" must be read as "is it possible"? And what is $\epsilon$? $\endgroup$
    – Fedor Petrov
    Commented Oct 7, 2018 at 20:07
  • $\begingroup$ what does it mean "$\epsilon$ is a positive constant depends on $n$?" $\endgroup$
    – Fedor Petrov
    Commented Oct 7, 2018 at 20:53
  • $\begingroup$ in any case: you may construct the set by adding the elements one by one, this allows to get about $c\cdot n^{1/3}$ elements for free. Is it enough? $\endgroup$
    – Fedor Petrov
    Commented Oct 7, 2018 at 20:54

1 Answer 1

Reset to default
6
$\begingroup$

Such $X$ do indeed exist, and are explicitly constructed in I.Z. Ruzsa, Solving a linear equation in a set of integers, Acta Arith., LXV.3 (1993), pp. 259-282, Theorem 7.5. The whole paper is devoted to upper and lower bounds on sizes of solution-free sets to equations such as the one you are asking about. A mathscinet forward search from that paper should yield further results.

Improve this answer
$\endgroup$
3
  • 5
    $\begingroup$ specifically Theorem 7.5 in this paper seems to the answer original question $\endgroup$
    – Fedor Petrov
    Commented Oct 8, 2018 at 14:36
  • $\begingroup$ Thank you, Fedor! I knew that the answer was in there, but did not have time this morning to find the exact place. I have updated the answer. $\endgroup$
    – Alex B.
    Commented Oct 8, 2018 at 16:10
  • $\begingroup$ @Kim: you can just ask a separate question here on MO. I am unlikely to be of much help. It has been 13 years since I read that paper - I was a 2nd year undergraduate. $\endgroup$
    – Alex B.
    Commented Oct 24, 2018 at 21:03

You must log in to answer this question.

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