Let $f$ be a computable function from prime numbers to non-negative integers such that$$\frac{f(p)-p}{\sqrt{p}}$$is bounded from above and below.
Is there an algebraic curve such that $f$ is the number of its points modulo primes?
Can we at least find a curve such that the number of points and $f$ disagree only for finitely many primes?
As a special case can $f(p)=p+1$ be realized? It may not mesh well with Sato-Tate.
Edit The original diagonalization argument function I gave didn't satisfy the inequality. The following answer works.
A diagonalization argument works here to show there aren't! Take an enumeration $X_n$ of all curves defined over the integers (it is easy to write down a computable such) and let $$f(p_n) = \begin{cases} p_n, &|X_n(\mathbb{F}_{p_n})| \neq p_n\\ p_n+1, & \mathrm{else}\end{cases}.$$
Indeed $f(p)= p+1$ cannot be realized by any curve except $\mathbb P^1$ (which I guess is what you meant, since, as Yosemite Sam points out, it can certainly be realized by $\mathbb P^1$).
In fact, if $C$ is a curve such that the number of points of $C$ mod $p$ minus $p$ is bounded, then $C $ is a curve of genus $0$ and has exactly $p+1$ points mod any $p$ where it has good reduction.
You mention Sato-Tate, which could indeed be used to prove this if it was known in suitable generality, but it is nothing more than a conjecture beyond the genus $1$ cases and a little bit of $2$.
Instead, you want to use mod $\ell$ and $\ell$-adic equidistribution, which follows from the Chebotarev density theorem.
Let $C$ be a curve, and suppose the difference between the number of points of $C$ over $\mathbb F_p$ and $p+1$ is bounded by $B$, so in particular is $-B,\dots, B$. For any $n$, the trace of Frobenius on the $\ell^n$-torsion points of the Jacobian of the curve is in $\{-B, \dots, B\}$.
The action of the Galois group on the $\ell^n$-torsion points factors through a finite group, and by Chebotarev, every element of that group arises from a Frobenius, so in fact every element of the Galois group acts on the $\ell^n$-torsion points with trace in $\{-B, \dots, B\}$.
Taking the limit as $n$ goes to $\infty$, every element of the Galois group acts on the $\ell$-adic Tate module with trace in $\{-B, \dots, B\}$, where we use crucially that $\{-B, \dots, B\}$ is closed in the $\ell$-adic topology. In particular, every power of Frobenius has trace bounded by $B$. This implies the eigenvalues of Frobenius on the $\ell$-adic Tate module are roots of unity, which contradicts Weil's Riemann hypothesis for the curve, or, more simply, contradicts the existence of the Weil pairing, unless there are no eigenvalues at all, in which case the genus is $0$, as desired.
You can read about this kind of reasoning in Serre's book $N_X(p)$. A version of this result may even be in there.
