8
$\begingroup$

Let $\mathbb{F}_p$ be a finite field, $A=\{a_1,\dots,a_k\}\subset\mathbb{F}_p^*$ a $k$-element set, for $k<p$. $\mathfrak{S}_k=$permutation gp.

Question. Is it true there is always a $\pi\in\mathfrak{S}_k$ such that the following are pair-wise distinct in $\mathbb{F}_p$? $$a_{\pi(1)}, \,a_{\pi(1)}+a_{\pi(2)},\,a_{\pi(1)}+a_{\pi(2)}+a_{\pi(3)},\,\dots, \,a_{\pi(1)}+\cdots+a_{\pi(k)}.$$

EDIT. Due to Julian Rosen's example, I change $A$ to be a subset of $\mathbb{F}_p^*$ (non-zero elements).

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ $A=\{0,1,-1\}$ is a counterexample. $\endgroup$
    – Julian Rosen
    Mar 19, 2017 at 15:25
  • $\begingroup$ What if we remove $0$? $\endgroup$
    – T. Amdeberhan
    Mar 19, 2017 at 16:15
  • 1
    $\begingroup$ More generally, take A disjoint union -A for certain A: you won't get much more than half way without getting a repeat. (Actually, that may not hold. Hmm.) Gerhard "Wonders About Big Uncertain A" Paseman, 2017.03.19. $\endgroup$
    – Gerhard Paseman
    Mar 19, 2017 at 16:17
  • 8
    $\begingroup$ This is actually a known open problem. I do not have any reference (and not sure anything has been published on it, just because there are no results to publish, as far as I am aware), but I remember for instance discussing it with Yong-Gao Chen and Zhi-Wei Sun a year and a half ago. $\endgroup$
    – Seva
    Mar 19, 2017 at 16:48
  • $\begingroup$ is symmetric gp = $S_k$ the symmetric group on $k$ elements? $\endgroup$
    – yberman
    Mar 19, 2017 at 20:15

2 Answers 2

Reset to default
10
$\begingroup$

It took me some effort to find the references you were requesting in your comment, but here they are eventually:

As one can see, the problem is around for over 15 years at least.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Wow! That is incredible. Thanks for the resources. $\endgroup$
    – T. Amdeberhan
    Mar 20, 2017 at 16:27
6
$\begingroup$

I first learned about this problem from Éric Balandraud (in 2013). So I wrote to him a couple of days ago, and he has just sent me an e-mail explaining that the question dates back (at least) to 1971. Éric attributes it to Erdős and Graham: He hasn't provided me with a reference (he is in the desert these days), but I will come back and update this answer as soon as I hear from him again.

Update (March 31, 2017). I've just got a new message from Éric Balandraud. Below is an excerpt.

Here is the reference:

R. Graham, On sums of integers taken from a fixed sequences, Proc. Wash. State Univ. Conf. on Number Theory (1971), 22-40.

The question is stated as Conjecture 10 on page 36. It also appears in:

P. Erdős and R. Graham, Old and new problems and results in combinatorial number theory, Monographie N28 de L'Enseignement Mathématiques, Université de Genève (1980).

The conjecture is stated there on page 95.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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