Subcontests
(5)A+A ⊃ squares
Let n be a positive integer and A a set of integers such that the set {x=a+b ∣ a,b∈A} contains {12,22,…,n2}. Prove that there is a positive integer N such that if n≥N, then ∣A∣>n0.666. Pseudo-determinant functions in finite field
For a positive integer n, we say an n-shuffling is a bijection σ:{1,2,…,n}→{1,2,…,n} such that there exist exactly two elements i of {1,2,…,n} such that σ(i)=i.Fix some three pairwise distinct n-shufflings σ1,σ2,σ3. Let q be any prime, and let Fq be the integers modulo q. Consider all functions f:(Fqn)n→Fq that satisfy, for all integers i with 1≤i≤n and all x1,…xi−1,xi+1,…,xn,y,z∈Fqn, f(x1,…,xi−1,y,xi+1,…,xn)+f(x1,…,xi−1,z,xi+1,…,xn)=f(x1,…,xi−1,y+z,xi+1,…,xn), and that satisfy, for all x1,…,xn∈Fqn and all σ∈{σ1,σ2,σ3}, f(x1,…,xn)=−f(xσ(1),…,xσ(n)).
For a given tuple (x1,…,xn)∈(Fqn)n, let g(x1,…,xn) be the number of different values of f(x1,…,xn) over all possible functions f satisfying the above conditions.
Pick (x1,…,xn)∈(Fqn)n uniformly at random, and let ε(q,σ1,σ2,σ3) be the expected value of g(x1,…,xn). Finally, let κ(σ1,σ2,σ3)=−q→∞limlogq(−ln(q−1ε(q,σ1,σ2,σ3)−1)).Pick three pairwise distinct n-shufflings σ1,σ2,σ3 uniformly at random from the set of all n-shufflings. Let π(n) denote the expected value of κ(σ1,σ2,σ3). Suppose that p(x) and q(x) are polynomials with real coefficients such that q(−3)=0 and such that π(n)=q(n)p(n) for infinitely many positive integers n. Compute q(−3)p(−3).