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).

$\endgroup$
  • 3
    $\begingroup$ $A=\{0,1,-1\}$ is a counterexample. $\endgroup$ – Julian Rosen Mar 19 '17 at 15:25
  • $\begingroup$ What if we remove $0$? $\endgroup$ – T. Amdeberhan Mar 19 '17 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 '17 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 '17 at 16:48
  • $\begingroup$ is symmetric gp = $S_k$ the symmetric group on $k$ elements? $\endgroup$ – yberman Mar 19 '17 at 20:15
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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Wow! That is incredible. Thanks for the resources. $\endgroup$ – T. Amdeberhan Mar 20 '17 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.


| cite | improve this answer | |
$\endgroup$

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.