{
  "id": "2308.04284",
  "version": "v1",
  "published": "2023-08-08T14:25:28.000Z",
  "updated": "2023-08-08T14:25:28.000Z",
  "title": "A Littlewood-Offord kind of problem in $\\mathbb{Z}_p$ and $Γ$-sequenceability",
  "authors": [
    "Simone Costa"
  ],
  "categories": [
    "math.CO",
    "math.NT",
    "math.PR"
  ],
  "abstract": "The Littlewood-Offord problem is a classical question in probability theory and discrete mathematics, proposed, firstly by Littlewood and Offord in the 1940s. Given a set $A$ of integer, this problem asks for an upper bound on the probability that a randomly chosen subset $X$ of $A$ sums to an integer $x$. This article proposes a variation of the problem, considering a subset $A$ of a cyclic group of prime order and examining subsets $X\\subseteq A$ of a given cardinality $\\ell$. The main focus of this paper is then on bounding the probability distribution of the sum $Y$ of $\\ell$ i.i.d. $Y_1,\\dots, Y_{\\ell}$ whose support is contained in $\\mathbb{Z}_p$. The main result here presented is that, if the probability distributions of the variables $Y_i$ are bounded by $\\lambda \\leq 9/10$, then, assuming that $p> \\frac{2}{\\lambda}\\left(\\frac{\\ell_0}{3}\\right)^{\\nu}$ (for some $\\ell_0\\leq\\ell$), the distribution of $Y$ is bounded by $\\lambda\\left(\\frac{3}{\\ell_0}\\right)^{\\nu}$ for some positive absolute constant $\\nu$. Then an analogous result is implied for the Littlewood-Offord problem over $\\mathbb{Z}_p$ on subsets $X$ of a given cardinality $\\ell$ in the regime where $n$ is large enough. Finally, as an application of our results, we propose a variation of the set-sequenceability problem: that of $\\Gamma$-sequenceability. Given a graph $\\Gamma$ on the vertex set $\\{1,2,\\dots,n\\}$ and given a subset $A\\subseteq \\mathbb{Z}_p$ of size $n$, here we want to find an ordering of $A$ such that the partial sums $s_i$ and $s_j$ are different whenever $\\{i,j\\}\\in E(\\Gamma)$. As a consequence of our results on the Littlewood-Offord problem, we have been able to prove that, if the maximum degree of $\\Gamma$ is at most $d$, $n$ is large enough, and $p>n^2$, any subset $A\\subseteq \\mathbb{Z}_p$ of size $n$ is $\\Gamma$-sequenceable.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-08-08T14:25:28.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "11B75",
      "60G50",
      "05C38",
      "05D40"
    ],
    "keywords": [
      "littlewood-offord kind",
      "littlewood-offord problem",
      "sequenceability",
      "probability distribution",
      "discrete mathematics"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}