Problem Statement:
We are considering the function: f(x, y) = |6xy + x + y|
where x and y are non-zero integers, i.e., x, y are integers and x ≠ 0, y ≠ 0.
Our goal is to prove that there are infinitely many positive integers k not in the image of this function. That is, we want to show that the set K = { k is a positive integer : k is not in { |6xy + x + y| where x, y are non-zero integers } } is infinite.
Proof Sketch (Using Density Argument):
Let S be the image of the function f, i.e., S = { |6xy + x + y| where x, y are non-zero integers }. We aim to show that the set of positive integers not in S is infinite.
- Reformulate the Function’s Output:
The expression inside the absolute value can be algebraically manipulated:
6xy + x + y = (1/6) * (36xy + 6x + 6y) = (1/6) * ( (6x+1)(6y+1) – 1 )
Let X = 6x+1 and Y = 6y+1.
Since x, y are non-zero integers:
If x ≥ 1, then 6x+1 can be 7, 13, 19, …
If x ≤ -1, then 6x+1 can be -5, -11, -17, …
So, X and Y must be integers of the form 6m+1 for some non-zero integer m.
Let Q = { 6m+1 | m is a non-zero integer }. Note that 1 is not in Q (since m cannot be 0).
The values k in the image S are of the form k = | (XY-1)/6 | for some X, Y in Q. - Relate Image Values to Products:
For a positive integer k to be in the image S, we must have 6k = |XY-1|. This leads to two possibilities for the product XY:
a) XY – 1 = 6k implies XY = 6k+1
b) XY – 1 = -6k implies XY = 1-6k
Let P = Q * Q = { u*v | u,v are in Q } be the set of all possible products of two elements from Q.
Thus, k is in S if and only if either 6k+1 is in P or 1-6k is in P. - Estimate the Number of Image Values up to M:
Let S_M = { k in S | 1 ≤ k ≤ M }. We want to estimate the size of this set, |S_M|.
If k is in S_M, then 1 ≤ k ≤ M.
The corresponding product XY in P must satisfy:
a) For XY = 6k+1: Since 1 ≤ k ≤ M, then 7 ≤ 6k+1 ≤ 6M+1. So, |XY| ≤ 6M+1.
b) For XY = 1-6k: Since 1 ≤ k ≤ M, then 1-6k is between 1-6 = -5 and 1-6M. So, |XY| = |1-6k| = 6k-1 < 6M.
In both cases, any product XY in P that generates a value k in S_M must satisfy |XY| ≤ 6M+1. - Apply Results on the Density of Products (Multiplication Table Problem):
Let P_L = { Z in P | |Z| ≤ L }.
The number of distinct integers that can be formed as a product of two integers (from a sufficiently dense set like an arithmetic progression) up to a certain magnitude L is known to be significantly less than L. Standard results in analytic number theory (related to the “multiplication table problem” studied by Erdős, Ford, and others) show that the number of distinct products uv with |uv| ≤ L is “little-oh of L”, denoted o(L). More specifically, this count is O(L / (log L)^c) for some positive constant c (e.g., c is approximately 0.086).
The set Q consists of integers in an arithmetic progression 6m+1 (excluding m=0). The number of distinct products XY in P such that |XY| ≤ L (i.e., |P_L|) follows this o(L) behavior. Thus, |P_L| = O(L / (log L)^c). - Bound |S_M|:
Each value Z in P where |Z| ≤ 6M+1 can correspond to at most one positive integer k in S_M.
If Z = 6k+1, then k=(Z-1)/6. If Z=1-6k’, then k’=(1-Z)/6. (Since X,Y are in Q, XY ≠ 1, so Z ≠ 1, meaning k, k’ are well-defined and positive).
The number of distinct k values in S_M is bounded by the number of distinct Z values in P that could generate them.
|S_M| ≤ 2 * |P_{6M+1}| (the factor 2 is a generous upper bound considering Z=6k+1 and Z=1-6k).
So, |S_M| ≤ O( (6M+1) / (log(6M+1))^c ) = O( M / (log M)^c ). - Determine the Asymptotic Density of S:
The asymptotic density of the set S in the set of positive integers is defined as the limit of |S_M|/M as M approaches infinity.
Limit (as M → ∞) of [ O( M / (log M)^c ) / M ]
= Limit (as M → ∞) of [ O( 1 / (log M)^c ) ]
Since c > 0, (log M)^c approaches infinity as M approaches infinity. Therefore, the limit is 0. - Conclusion:
The set S (the image of the function f) has an asymptotic density of 0 in the set of positive integers. This means that the proportion of positive integers up to M that are in S tends to zero as M becomes very large.
If S has density 0, its complement in the positive integers (the set of positive integers not in the image) must have density 1 – 0 = 1. A set with density 1 is necessarily an infinite set.
Therefore, there are infinitely many positive integers k not in the image of the function f(x,y) = |6xy+x+y| for non-zero integers x, y.
Q.E.D.