Existence of Solutions of mixed Linear-Quadratic Equation System modulo $p$

Question

I need some help on the existence of solutions of an equation system modulo some prime $p$. The equation system has three parametes $n$, $N$ and $p$ and the equations are of the form $$ \sum_{i=1}^n x_i^d = 1 \bmod p \qquad \text{for $d = 1, \dots, N$.} $$ The $x_i$ are elements of $\mathbb{Z}_p$. A trivial solution to this equation system is a solution of the form $x_i = 0$ for all $i \neq k$ and $x_k = 1$ where $k \in \{1,\dots, n\}$ is a randomly chosen index.

As @Peter pointed out, for $p=11$, $n=3$ and $N=2$ there is a non-tivial solution $x_1 = 2$, $x_2 = 4$ and $x_3 = 6$. In the meantime, I also found a lot of other examples for $n=3$, $N=2$ and different $p$.

I am interested in the following: Is there a criterion on $n$, $N$ and $p$ to easily decide if there is a non-trivial solution?

And, assume I challenge you and give you $p$, $n$ and $N$ for which a non-trivial solution exists, how efficient can you find such a non-trivial solution? (In dependence of $n$, $N$ and $p$)

Is there an estimate on the number of non-trivial solutions?

I'm happy for any advice or pointers to relevant papers.

Answer 1

This is not a mathematical answer, but merely a program for brute-forcing. Hopefully, someone will use this to find a pattern and explain it mathematically. I am adding it as an answer, as it's too long for a comment.

Python code:

from itertools import product 
from itertools import chain
def run(p,n,tryToRemoveDuplicates=True):
    l=product(*([list(range(p))]*n))
    l_new=[]
    for k in l:
        if sum(k)%p==1 and sum([a*a for a in k])%p==1: 
            l_new.append(tuple(sorted(list(k))))
            if not tryToRemoveDuplicates: print(k)
    if tryToRemoveDuplicates:
        l=set(l_new)
        for k in l: 
            print(k)

#examples
print("For p=5, n=7")
run(5,7)
print("For p=5, n=11")
run(5,7,tryToRemoveDuplicates=False)

The $\text{run}$ function takes as parameters $p$ and $n$ and an optional boolean. If the boolean value is True, the program will try to remove duplicates (but setting it to False is better for larger $n$)

For $p=5$, $n=7$, we get:

(1, 2, 3, 3, 4, 4, 4)
(0, 0, 0, 2, 3, 3, 3)
(1, 1, 2, 2, 2, 4, 4)
(0, 0, 0, 0, 3, 4, 4)
(0, 0, 2, 2, 4, 4, 4)
(0, 0, 0, 0, 0, 0, 1)
(0, 0, 1, 1, 2, 3, 4)
(1, 1, 1, 3, 3, 3, 4)
(0, 1, 4, 4, 4, 4, 4)
(0, 1, 1, 1, 1, 1, 1)
(0, 1, 3, 3, 3, 3, 3)
(0, 2, 2, 2, 3, 3, 4)
(1, 1, 1, 1, 2, 2, 3)
(0, 1, 2, 2, 2, 2, 2)