Skip to main content

How many rich directions does a set in $\mathbb F_p^2$ determinesdetermine?

$\newcommand{\F}{\mathbb F}$ A subset $P$ of the affine plane $\F_p^2$ is said to determine a direction if there is a line in this direction containing at least two points of $P$.

A set of size $|P|>p$ determines all $p+1$ directions, a set of size $|P|\le p$ not contained in a single line determines at least $(|P|+3)/2$ directions; the former is an immediate consequence of the pigeonhole principle, the latter is a highly non-trivial result of Szonyi that builds on works of Rédei.

Let's say that a direction in $\F_p^2$ is rich if there is a line in this direction containing at least three points of $P$. If $P$ is trapped in a line, or a union of two lines, then there are just one or two rich directions.

What is the smallest possible number of rich directions for a set $P\subset\F_p^2$ of size $\frac53\,p<|P|\le 2p$ given that $P$ is not contained in a union of two lines?

It is easy to construct sets $P$ with about $|P|-p$ rich directions, but it is not clear to me how much better can one do.

Added May 04, 2018

The largest possible number of points in general position in $\F_p^2$ is $p+1$, which is quite easy to prove; thus, we are guaranteed to have at least one rich direction. Indeed, I can show that if $\frac32(1+\delta)p\le|P|\le 2p$, then there are at least $\Omega_\delta(\sqrt p)$ rich directions, but I suspect that this can be far from being sharp.

How many rich directions a set in $\mathbb F_p^2$ determines?

$\newcommand{\F}{\mathbb F}$ A subset $P$ of the affine plane $\F_p^2$ is said to determine a direction if there is a line in this direction containing at least two points of $P$.

A set of size $|P|>p$ determines all $p+1$ directions, a set of size $|P|\le p$ not contained in a single line determines at least $(|P|+3)/2$ directions; the former is an immediate consequence of the pigeonhole principle, the latter is a highly non-trivial result of Szonyi.

Let's say that a direction in $\F_p^2$ is rich if there is a line in this direction containing at least three points of $P$. If $P$ is trapped in a line, or a union of two lines, then there are just one or two rich directions.

What is the smallest possible number of rich directions for a set $P\subset\F_p^2$ of size $\frac53\,p<|P|\le 2p$ given that $P$ is not contained in a union of two lines?

It is easy to construct sets $P$ with about $|P|-p$ rich directions, but it is not clear to me how much better can one do.

Added May 04, 2018

The largest possible number of points in general position in $\F_p^2$ is $p+1$, which is quite easy to prove; thus, we are guaranteed to have at least one rich direction. Indeed, I can show that if $\frac32(1+\delta)p\le|P|\le 2p$, then there are at least $\Omega_\delta(\sqrt p)$ rich directions, but I suspect that this can be far from being sharp.

How many rich directions does a set in $\mathbb F_p^2$ determine?

$\newcommand{\F}{\mathbb F}$ A subset $P$ of the affine plane $\F_p^2$ is said to determine a direction if there is a line in this direction containing at least two points of $P$.

A set of size $|P|>p$ determines all $p+1$ directions, a set of size $|P|\le p$ not contained in a single line determines at least $(|P|+3)/2$ directions; the former is an immediate consequence of the pigeonhole principle, the latter is a highly non-trivial result of Szonyi that builds on works of Rédei.

Let's say that a direction in $\F_p^2$ is rich if there is a line in this direction containing at least three points of $P$. If $P$ is trapped in a line, or a union of two lines, then there are just one or two rich directions.

What is the smallest possible number of rich directions for a set $P\subset\F_p^2$ of size $\frac53\,p<|P|\le 2p$ given that $P$ is not contained in a union of two lines?

It is easy to construct sets $P$ with about $|P|-p$ rich directions, but it is not clear to me how much better can one do.

Added May 04, 2018

The largest possible number of points in general position in $\F_p^2$ is $p+1$, which is quite easy to prove; thus, we are guaranteed to have at least one rich direction. Indeed, I can show that if $\frac32(1+\delta)p\le|P|\le 2p$, then there are at least $\Omega_\delta(\sqrt p)$ rich directions, but I suspect that this can be far from being sharp.

added 145 characters in body
Source Link
Seva
  • 23k
  • 2
  • 59
  • 141

$\newcommand{\F}{\mathbb F}$ A subset $P$ of the affine plane $\F_p^2$ is said to determine a direction if there is a line in this direction containing at least two points of $P$.

A set of size $|P|>p$ determines all $p+1$ directions, a set of size $|P|\le p$ not contained in a single line determines at least $(|P|+3)/2$ directions; the former is an immediate consequence of the pigeonhole principle, the latter is a highly non-trivial result of Szonyi.

Let's say that a direction in $\F_p^2$ is rich if there is a line in this direction containing at least three points of $P$. If $P$ is trapped in a line, or a union of two lines, then there are just one or two rich directions.

What is the smallest possible number of rich directions for a set $P\subset\F_p^2$ of size $\frac53\,p<|P|\le 2p$ given that $P$ is not contained in a union of two lines?

It is easy to construct sets $P$ with about $|P|-p$ rich directions, but it is not clear to me how much better can one do.

Added May 04, 2018

The largest possible number of points in general position in $\F_p^2$ is $p+1$, which is quite easy to prove; thus, we are guaranteed to have at least one rich direction. Can the number of rich directions stay bounded asIndeed, I can show that if $p$ grows?$\frac32(1+\delta)p\le|P|\le 2p$, then there are at least $\Omega_\delta(\sqrt p)$ rich directions, but I suspect that this can be far from being sharp.

$\newcommand{\F}{\mathbb F}$ A subset $P$ of the affine plane $\F_p^2$ is said to determine a direction if there is a line in this direction containing at least two points of $P$.

A set of size $|P|>p$ determines all $p+1$ directions, a set of size $|P|\le p$ not contained in a single line determines at least $(|P|+3)/2$ directions; the former is an immediate consequence of the pigeonhole principle, the latter is a highly non-trivial result of Szonyi.

Let's say that a direction in $\F_p^2$ is rich if there is a line in this direction containing at least three points of $P$. If $P$ is trapped in a line, or a union of two lines, then there are just one or two rich directions.

What is the smallest possible number of rich directions for a set $P\subset\F_p^2$ of size $\frac53\,p<|P|\le 2p$ given that $P$ is not contained in a union of two lines?

It is easy to construct sets $P$ with about $|P|-p$ rich directions, but it is not clear to me how much better can one do.

The largest possible number of points in general position in $\F_p^2$ is $p+1$, which is quite easy to prove; thus, we are guaranteed to have at least one rich direction. Can the number of rich directions stay bounded as $p$ grows?

$\newcommand{\F}{\mathbb F}$ A subset $P$ of the affine plane $\F_p^2$ is said to determine a direction if there is a line in this direction containing at least two points of $P$.

A set of size $|P|>p$ determines all $p+1$ directions, a set of size $|P|\le p$ not contained in a single line determines at least $(|P|+3)/2$ directions; the former is an immediate consequence of the pigeonhole principle, the latter is a highly non-trivial result of Szonyi.

Let's say that a direction in $\F_p^2$ is rich if there is a line in this direction containing at least three points of $P$. If $P$ is trapped in a line, or a union of two lines, then there are just one or two rich directions.

What is the smallest possible number of rich directions for a set $P\subset\F_p^2$ of size $\frac53\,p<|P|\le 2p$ given that $P$ is not contained in a union of two lines?

It is easy to construct sets $P$ with about $|P|-p$ rich directions, but it is not clear to me how much better can one do.

Added May 04, 2018

The largest possible number of points in general position in $\F_p^2$ is $p+1$, which is quite easy to prove; thus, we are guaranteed to have at least one rich direction. Indeed, I can show that if $\frac32(1+\delta)p\le|P|\le 2p$, then there are at least $\Omega_\delta(\sqrt p)$ rich directions, but I suspect that this can be far from being sharp.

added 234 characters in body; edited title
Source Link
Seva
  • 23k
  • 2
  • 59
  • 141

How many rich directions determines a set in $\mathbb F_p^2$ determines?

$\newcommand{\F}{\mathbb F}$

A A subset $P$ of the affine plane $\F_p^2$ is said to determine a direction if there is a line in this direction containing at least two points of $P$.

A set of size $|P|>p$ determines all $p+1$ directions, a set of size $|P|\le p$ not contained in a single line determines at least $(|P|+3)/2$ directions; the former is an immediate consequence of the pigeonhole principle, the latter is a highly non-trivial result of Szonyi.

Let's say that a direction in $\F_p^2$ is rich if there is a line in this direction containing at least three points of $P$. If $P$ is trapped in a line, or a union of two lines, then there are just one or two rich directions.

What is the smallest possible number of rich directions for a set $P\subset\F_p^2$ of size $\frac53\,p<|P|\le 2p$ given that $P$ is not contained in a union of two lines?

It is easy to construct sets $P$ with about $|P|-p$ rich directions, but it is not clear to me how much better can one do.

The largest possible number of points in general position in $\F_p^2$ is $p+1$, which is quite easy to prove; thus, we are guaranteed to have at least one rich direction. Can the number of rich directions stay bounded as $p$ grows?

How many rich directions determines a set in $\mathbb F_p^2$?

$\newcommand{\F}{\mathbb F}$

A subset $P$ of the affine plane $\F_p^2$ is said to determine a direction if there is a line in this direction containing at least two points of $P$.

A set of size $|P|>p$ determines all $p+1$ directions, a set of size $|P|\le p$ not contained in a single line determines at least $(|P|+3)/2$ directions; the former is an immediate consequence of the pigeonhole principle, the latter is a highly non-trivial result of Szonyi.

Let's say that a direction in $\F_p^2$ is rich if there is a line in this direction containing at least three points of $P$. If $P$ is trapped in a line, or a union of two lines, then there are just one or two rich directions.

What is the smallest possible number of rich directions for a set $P\subset\F_p^2$ of size $\frac53\,p<|P|\le 2p$ given that $P$ is not contained in a union of two lines?

It is easy to construct sets $P$ with about $|P|-p$ rich directions, but it is not clear to me how much better can one do.

How many rich directions a set in $\mathbb F_p^2$ determines?

$\newcommand{\F}{\mathbb F}$ A subset $P$ of the affine plane $\F_p^2$ is said to determine a direction if there is a line in this direction containing at least two points of $P$.

A set of size $|P|>p$ determines all $p+1$ directions, a set of size $|P|\le p$ not contained in a single line determines at least $(|P|+3)/2$ directions; the former is an immediate consequence of the pigeonhole principle, the latter is a highly non-trivial result of Szonyi.

Let's say that a direction in $\F_p^2$ is rich if there is a line in this direction containing at least three points of $P$. If $P$ is trapped in a line, or a union of two lines, then there are just one or two rich directions.

What is the smallest possible number of rich directions for a set $P\subset\F_p^2$ of size $\frac53\,p<|P|\le 2p$ given that $P$ is not contained in a union of two lines?

It is easy to construct sets $P$ with about $|P|-p$ rich directions, but it is not clear to me how much better can one do.

The largest possible number of points in general position in $\F_p^2$ is $p+1$, which is quite easy to prove; thus, we are guaranteed to have at least one rich direction. Can the number of rich directions stay bounded as $p$ grows?

added 31 characters in body
Source Link
Seva
  • 23k
  • 2
  • 59
  • 141
Loading
Source Link
Seva
  • 23k
  • 2
  • 59
  • 141
Loading