Skip to main content
deleted 238 characters in body
Source Link
Seva
  • 23k
  • 2
  • 59
  • 141

This is the "real-life" (but slightly more technical) version of a question I have asked recently.

For a prime $p>10$, let $\mathcal L_X$, $\mathcal L_Y$, and $\mathcal L_Z$ denote the pencils of all those lines in $\mathbb F_p^2$ parallel to the lines $$ X:=\{(x,0)\colon x\in\mathbb F_p \}, \ Y:=\{(0,y)\colon y\in\mathbb F_p \}, \ Z:=\{(z,z)\colon z\in\mathbb F_p \}, $$ respectively; thus, $|\mathcal L_X|=|\mathcal L_Y|=|\mathcal L_Z|=p$. Write $$ \chi(x,y) := \omega^x,\quad (x,y)\in\mathbb F_p^2, $$ where $\omega$ is a fixed primitive root of unity of degree $p$. Given a set $S\subseteq\mathbb F_p^2$, with every element $s\in S$ associate a formal variable $x_s$, and consider the system of homogeneous linear equations \begin{gather*} \sum_{s\in S\cap\ell} x_s = 0,\quad \ell\in\mathcal L_X\cup\mathcal L_Y, \\ \sum_{s\in S\cap\ell} \chi(s)\,x_s=0, \quad \ell \in \mathcal L_Z; \end{gather*} notice that there are $3p$ equations and $|S|$ variables. Does there exist a set $S\subseteq\mathbb F_p^2$ of size $|S|<3p$ for which this system has a non-zero solution?

In case it helps, it can be assumed that the solution actually has a much stronger property than just being non-trivial; namely,such that the set $\{s\in S\colon x_s\ne 0\}$ meets every line in $\mathbb F_p^2$, as a result of which the solution vector $\{x_s\}_{s\in S}$ has at least $2p-1$ non-zero components.?

This is the "real-life" (but slightly more technical) version of a question I have asked recently.

For a prime $p>10$, let $\mathcal L_X$, $\mathcal L_Y$, and $\mathcal L_Z$ denote the pencils of all those lines in $\mathbb F_p^2$ parallel to the lines $$ X:=\{(x,0)\colon x\in\mathbb F_p \}, \ Y:=\{(0,y)\colon y\in\mathbb F_p \}, \ Z:=\{(z,z)\colon z\in\mathbb F_p \}, $$ respectively; thus, $|\mathcal L_X|=|\mathcal L_Y|=|\mathcal L_Z|=p$. Write $$ \chi(x,y) := \omega^x,\quad (x,y)\in\mathbb F_p^2, $$ where $\omega$ is a fixed primitive root of unity of degree $p$. Given a set $S\subseteq\mathbb F_p^2$, with every element $s\in S$ associate a formal variable $x_s$, and consider the system of homogeneous linear equations \begin{gather*} \sum_{s\in S\cap\ell} x_s = 0,\quad \ell\in\mathcal L_X\cup\mathcal L_Y, \\ \sum_{s\in S\cap\ell} \chi(s)\,x_s=0, \quad \ell \in \mathcal L_Z; \end{gather*} notice that there are $3p$ equations and $|S|$ variables. Does there exist a set $S\subseteq\mathbb F_p^2$ of size $|S|<3p$ for which this system has a non-zero solution?

In case it helps, it can be assumed that the solution actually has a much stronger property than just being non-trivial; namely, that the set $\{s\in S\colon x_s\ne 0\}$ meets every line in $\mathbb F_p^2$, as a result of which the solution vector $\{x_s\}_{s\in S}$ has at least $2p-1$ non-zero components.

This is the "real-life" (but slightly more technical) version of a question I have asked recently.

For a prime $p>10$, let $\mathcal L_X$, $\mathcal L_Y$, and $\mathcal L_Z$ denote the pencils of all those lines in $\mathbb F_p^2$ parallel to the lines $$ X:=\{(x,0)\colon x\in\mathbb F_p \}, \ Y:=\{(0,y)\colon y\in\mathbb F_p \}, \ Z:=\{(z,z)\colon z\in\mathbb F_p \}, $$ respectively; thus, $|\mathcal L_X|=|\mathcal L_Y|=|\mathcal L_Z|=p$. Write $$ \chi(x,y) := \omega^x,\quad (x,y)\in\mathbb F_p^2, $$ where $\omega$ is a fixed primitive root of unity of degree $p$. Given a set $S\subseteq\mathbb F_p^2$, with every element $s\in S$ associate a formal variable $x_s$, and consider the system of homogeneous linear equations \begin{gather*} \sum_{s\in S\cap\ell} x_s = 0,\quad \ell\in\mathcal L_X\cup\mathcal L_Y, \\ \sum_{s\in S\cap\ell} \chi(s)\,x_s=0, \quad \ell \in \mathcal L_Z; \end{gather*} notice that there are $3p$ equations and $|S|$ variables. Does there exist a set $S\subseteq\mathbb F_p^2$ of size $|S|<3p$ for which this system has a solution such that the set $\{s\in S\colon x_s\ne 0\}$ meets every line in $\mathbb F_p^2$?

Source Link
Seva
  • 23k
  • 2
  • 59
  • 141

A system of homogeneous linear equations

This is the "real-life" (but slightly more technical) version of a question I have asked recently.

For a prime $p>10$, let $\mathcal L_X$, $\mathcal L_Y$, and $\mathcal L_Z$ denote the pencils of all those lines in $\mathbb F_p^2$ parallel to the lines $$ X:=\{(x,0)\colon x\in\mathbb F_p \}, \ Y:=\{(0,y)\colon y\in\mathbb F_p \}, \ Z:=\{(z,z)\colon z\in\mathbb F_p \}, $$ respectively; thus, $|\mathcal L_X|=|\mathcal L_Y|=|\mathcal L_Z|=p$. Write $$ \chi(x,y) := \omega^x,\quad (x,y)\in\mathbb F_p^2, $$ where $\omega$ is a fixed primitive root of unity of degree $p$. Given a set $S\subseteq\mathbb F_p^2$, with every element $s\in S$ associate a formal variable $x_s$, and consider the system of homogeneous linear equations \begin{gather*} \sum_{s\in S\cap\ell} x_s = 0,\quad \ell\in\mathcal L_X\cup\mathcal L_Y, \\ \sum_{s\in S\cap\ell} \chi(s)\,x_s=0, \quad \ell \in \mathcal L_Z; \end{gather*} notice that there are $3p$ equations and $|S|$ variables. Does there exist a set $S\subseteq\mathbb F_p^2$ of size $|S|<3p$ for which this system has a non-zero solution?

In case it helps, it can be assumed that the solution actually has a much stronger property than just being non-trivial; namely, that the set $\{s\in S\colon x_s\ne 0\}$ meets every line in $\mathbb F_p^2$, as a result of which the solution vector $\{x_s\}_{s\in S}$ has at least $2p-1$ non-zero components.