A Generalisation of Maximal (k,b)-Linear-Free Sets of Integers

1. Introduction

A set of integers $S$ is said to be $k$-multiple-free if $x\ne ky$ for all $x,y\in S$. Let $g_k(n)=max\{|A|:A\subseteq [n]:=\{1,2,\dots ,n\}\text{ is }k\text{-multiple-free}\}$. E.T.H Wang [1], when working on double-free sets, showed that $$g_2(n)=\lceil \frac{n}{2}\rceil +g_2\left(\lfloor \frac{n}{4}\rfloor \right),$$ with $g_2(0)=0$, and an asymptotic formula for $g_2(n)$ is given by $g_2(n)=\frac{2}{3}n+O(\log n)$. In a similar vein, Leung and Wei [2] proved that for every integer $r>1$, $g_r(n)=\frac{r}{r+1}n+O(\log n).$

Instead of $k$-multiple-free subsets, one can ask more general questions about a subset $S$ of $[n]$ such that: for any two elements $x$ and $y$ of $S,$ $\frac{y}{x}$ does not belong to $C,$ where $C$ is a fixed set of rational numbers. For example, when $C=\{2,3\},$ such a subset $S$ is called strongly triple-free, which is a subject of great interest in, for example, [3] and [4]. In fact, the genesis of this paper is the case when $C=\{k,k^2,\dots ,k^q\},$ where $k$ and $q$ are positive integers.

On the other hand, You, Yu, and Liu [5] studied an alternative, natural generalisation of multiple-free sets, which are translation-free, or linear-free sets. In particular, a set $X$ of integers is called $(k,b)$-linear-free if $x\in X$ implies $kx+b\notin X$. Obviously, when $b=0,$ $X$ is $k$-multiple-free. Define $g_{k,b}(n)=min\{|X|:X\subseteq [n]\text{ is amaximal }(k,b)\text{-linear-free subset}\}$ and $f_{k,b}(n)=max\{|X|:X\subseteq [n]\text{ is amaximal }(k,b)\text{-linear-free subset}\}$. You, Yu, and Liu proposed explicit formulae for the two functions and showed that there is a maximal $(k,b)$-linear-free subset of $[n]$ with exactly $x$ elements for any integer $x$ between the minimum and maximum possible orders. Moreover, Liu and Zhou [6] also dealt with the same generalisation, albeit having a different approach.

This paper extends the aforementioned results by combining those two concepts. Henceforth, $k,b,$ and $q$ will denote integers with $k\ge 2,b\ge 0,$ and $q\ge 2$. Define the function $p$ to be: $p(x)=kx+b$. A set $S$ of integers is said to be $(k,b,q)$-linear-free if $x\in S$ implies $p^i(x)\notin S,\mathrm{\forall }i=1,2,\dots ,q-1$, where $p^i(x)=p(p^{i-1}(x))$ and $p^0(x)=x$. Such a set $S$ is maximal in $[n]$ if $S\cup \{t\}$ is not $(k,b,q)$-linear-free for any $t\in [n]\mathrm{\setminus }S$. Let $M_{k,b,q}(n)$ be the set of all maximal $(k,b,q)$-linear-free subsets of $[n]$, and define $g_{k,b,q}(n)=\underset{S\in M_{k,b,q}(n)}{min}|S|$ and $f_{k,b,q}(n)=\underset{S\in M_{k,b,q}(n)}{max}|S|$. In this paper, formulae for $g_{k,b,q}(n)$ and $f_{k,b,q}(n)$ are derived. Also, it is proven that there is at least one maximal $(k,b,q)$-linear-free subset of $[n]$ of cardinality $x$ for any integer $x$ between $g_{k,b,q}(n)$ and $f_{k,b,q}(n)$, inclusively.

Notice that when $q=2$ we get back the notion of $(k,b)$-linear-free subsets: $f_{k,b,2}(n)=f_{k,b}(n)$ and $g_{k,b,2}(n)=g_{k,b}(n)$.

There is yet another classical way to look at the topic. For a fixed $r\times s$ integer matrix $\mathbf{\text{A}}$, let us call a subset $S_{\mathbf{\text{A}}}(n)\subseteq [n]$ A-missing if for every vector $\mathbf{\text{x}}=\left(\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_s\end{array}\right)$ with $x_i\in S_{\mathbf{\text{A}}}$ for all $i,$ the column vector $\mathbf{\text{Ax}}$ has none of its entries being equal to $0.$ With this definition, take $\mathbf{\text{A}}=\left(\begin{array}{cc}k& -1\end{array}\right)$ and $\mathbf{\text{B}}=\left(\begin{array}{ccc}2& -1& 0\\ 3& 0& -1\end{array}\right),$ then A-missing subsets and B-missing subsets are, respectively, $k$-multiple-free subsets and strongly triple-free subsets. Naturally, we can further fix a $r\times 1$ matrix b and look at the entries of $\mathbf{\text{Ax}}+\mathbf{\text{b}}$. We specify the $(q-1)\times q$ matrix $\mathbf{\text{A}}$ and the $(q-1)\times 1$ matrix $\mathbf{\text{b}}$ to be $$\mathbf{\text{A}}=\left(\begin{array}{ccccc}k& -1& 0& \dots & 0\\ k^2& 0& -1& \dots & 0\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ k^{q-1}& 0& 0& \dots & -1\end{array}\right)\text{and}\mathbf{\text{b}}=\left(\begin{array}{c}{p}^1(0)\\ p^2(0)\\ ⋮\\ p^{q-1}(0)\end{array}\right).$$ Interpreted in terms of matrices, a $(k,b,q)$-linear-free subset $S_{\mathbf{\text{A,b}}}(n)\subseteq [n]$ is equivalently a subset which satisfies: for every vector $\mathbf{\text{x}}=\left(\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_q\end{array}\right)$ with $x_i\in S_{\mathbf{\text{A,b}}}$ for all $i,$ the column vector $\mathbf{\text{Ax}}+\mathbf{\text{b}}$ has none of its entries being equal to $0.$ For instance, the case of $(k,b)$-linear-free subsets corresponds to $\mathbf{\text{A}}=\left(\begin{array}{cc}k& -1\end{array}\right)$ and $\mathbf{\text{b}}=\left(\begin{array}{c}b\end{array}\right),$ and none of the vectors $\mathbf{\text{x}}=\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)$ with $x_1,x_2\in S_{\mathbf{\text{A,b}}}$ is a solution to the equation $\mathbf{\text{Ax}}+\mathbf{\text{b}}=\mathbf{\text{0}}.$

2. Main Results

To simplify expressions, we denote $⟨k^i⟩=(k^i-1)/(k-1).$

Based on the proof of Theorem 1, a straightforward algorithm to construct a maximal $(k,b,q)$-linear-free subset $F$ of $[n]$ with $f_{k,b,q}(n)$ elements is proposed: first, check the largest number in $[n]$, which is $n$. As $p^i(n)\notin F,\mathrm{\forall }i=1,2,\dots ,q-1$, we add $n$ to $F$ (initially, $F$ is empty). Next, assume that we have checked until $x>1$. We then proceed to check $x-1$. If $p^i(x-1)\notin F,\mathrm{\forall }i=1,2,\dots ,q-1$, then $x-1$ is added to $F$. Otherwise, we proceed to check $x-2$. This algorithm terminates after number $1$ is checked.

The next theorem provides formulae to determine $f_{k,b,q}(n)$ and $g_{k,b,q}(n).$

It should be remarked that, by Theorem 1, $f_{k,b,q}\left(\lfloor \frac{n-b⟨k^{q(m+1)}⟩}{k^{q(m+1)}}\rfloor \right)$ is either $0$ or $\lfloor \frac{n-b⟨k^{q(m+1)}⟩}{k^{q(m+1)}}\rfloor ,$ depending on whether $\lfloor \frac{n-b⟨k^{q(m+1)}⟩}{k^{q(m+1)}}\rfloor$ is negative or not, and $g_{k,b,q}\left(\lfloor \frac{n-b⟨k^{(2q-1)(m+1)}⟩}{k^{(2q-1)(m+1)}}\rfloor \right)$ is determined correspondingly.

In Theorem 2, when $q=2$, formulae for $f_{k,b}(n)$ and $g_{k,b}(n)$ are obtained, which are, however, different from those of You, Yu, and Liu [5]. Particularly, You, Yu, and Liu suggested that $$f_{k,b}(n)=\sum _{i=1}^{n(1)}|N_i|\lceil \frac{i+1}{2}\rceil \text{and}{g}_{k,b}(n)=\sum _{i=1}^{n(1)}|N_i|\lceil \frac{i+1}{3}\rceil ,$$ where $n(1)=\lfloor {\log }_k\frac{n+b/(k-1)}{1+b/(k-1)}\rfloor$ and $$|N_i|=\{\begin{array}{ll}\lfloor \frac{n-b⟨k^i⟩}{k^i}\rfloor -2\lfloor \frac{n-b⟨k^{i+1}⟩}{k^{i+1}}\rfloor +\lfloor \frac{n-b⟨k^{i+2}⟩}{k^{i+2}}\rfloor & \text{for }i<n(1),\\ \lfloor \frac{n-b⟨k^i⟩}{k^i}\rfloor & \text{for }i=n(1).\end{array}$$ These are essentially different from Theorem 2 as the two have different strategies: our approach utilises recurrence relations while You, Yu, and Liu partition $[n]$ from the beginning. Furthermore, it seems that their approach can be suitably modified to accommodate for the more general cases when $q\ge 3.$

These somewhat complicated formulae are illustrated in the following example:

This is based on $$f_{k,0,q}(n)=\sum _{i\ge 0}\lceil \frac{k–1}{k}\lfloor \frac{n}{k^{qi}}\rfloor \rceil ,$$ which is a direct corollary of Theorem 2. In fact, Corollary 1 can be extended by generalising the method of Wakeham and Wood [7]. Particularly, for positive integers $a,b$ whose greatest common divisor is $g$ and $a<b$, one has $$f_{b/a,0,q}(n)=\frac{b^{q–1}(b–g)}{b^q–g^q}n+O(\log n).$$

Next, still in the case $b=0,$ if $n$ is a perfect power of $k$ then a much neater formula for $f_{k,0,q}(n)$ is as follows:

There is an alternative to determine $f_{k,0,q}(n)$. Partition $[n]$ into geometric progressions of the form $\{t,kt,k^{2}t,\dots ,k^{j}t\}$, where $t$ is not divisible by $k$ and $1\le t\le n$. Each such subset’s cardinality is $\lfloor {\log }_k(n/t)\rfloor +1.$ Within each subset, if its cardinality is $M$, then at most $\lceil M/q\rceil$ elements can belong to the same maximal $(k,0,q)$-linear-free subset of $[n]$. Therefore, $$f_{k,0,q}(n)=\sum _{\begin{array}{c}1\le t\le n\\ k\nmid t\end{array}}\lceil \frac{\lfloor {\log }_k(n/t)\rfloor +1}{q}\rceil .$$ Replacing $n$ with $k^{n-1}$, we obtain a result in The American Mathematical Monthly [8]:

Let $k,q$ and $n$ be positive integers with $k\ge 2$, and let $P$ be the set of all positive integers less than $k^n$ that are not divisible by $k$. Prove $$\sum _{p\in P}\lceil \frac{\lfloor n–{\log }_{k}p\rfloor }{q}\rceil =\lfloor \frac{k^{q–1}(k^{n–1}–1)(k–1)}{k^q–1}\rfloor +1.$$

Next, inspired by Theorem 2 in [5], we investigate the possible cardinalities of maximal $(k,b,q)$-linear-free subsets. The following lemma is crucial to the proof of Theorem 4.

This leads to

Lastly, we determine values of $n$ for which the lower bound and upper bound of the cardinalities of $(k,b,q)$-linear-free subsets of $[n]$ are, in fact, identical.

3. Further Research

For future research, it will be interesting to investigate the problem in a multi-dimensional space. For instance, one can start from the following generalisation for the double-free subsets:

Let $m$ and $n_1,n_2,\dots ,n_m$ be positive integers. Define $T=\{(x_1,x_2,\dots ,x_m):1\le x_i\le n_i,\mathrm{\forall }i=\overline{1,m}\}$. Let $g(n_1,\dots ,n_m)$ be the maximum number of lattice points one can choose from $T$ such that if $(x_1,\dots ,x_m)$ is chosen, then $(2x_1,\dots ,2x_m)$ is not. Determine $g(n_1,\dots ,n_m)$.

It can be proven that $$g(n_1,\dots ,n_m)=\prod _{i=1}^m{n}_i-\prod _{i=1}^m\lfloor \frac{n_i}{2}\rfloor +g(\lfloor \frac{n_1}{4}\rfloor ,\dots ,\lfloor \frac{n_m}{4}\rfloor ).$$ Hence, $$g(n_1,\dots ,n_m)=\sum _{i\ge 0}(-1{)}^i\prod _{j=1}^m\lfloor \frac{n_j}{2^i}\rfloor .$$

It is unclear whether Lemma 1 can be extended in this case, even to the Cartesian plane, which is critical to generalise Theorem 4.