Skip to main content
1 of 3
Peter Taylor
  • 7.2k
  • 1
  • 21
  • 29

A brief comment on notation: "can be averaged by" is a reflexive partial order. I shall use the notation $a \succeq b$ to indicate that $a$ can be averaged by $b$, and save $\geq$ for the usual total order on the integers.


Another partial answer, this time with a positive proposition which I'm calling the three-pass lemma:

If $a = mn$, $\exists s < n: sm \succeq b$, and $\exists t < m: tn \succeq b$ then $a \succeq b$.

Proof proceeds by arranging the $a$ values in $m$ rows of $n$ values each and then performing three passes:

  1. Average the first $t$ rows, then the next $t$ rows, etc. If $tn \not\mid a$, finish by averaging the last $t$ rows. At the end of this pass, every row contains a single value repeated $n$ times.
  2. Average the first $s$ columns, then the next $s$ columns, etc. If $sm \not\mid a$, finish by averaging the last $s$ columns. At the end of this pass, there only two distinct values remain: the first $n-s$ columns have one value, and the last $s$ columns have another.
  3. Repeat the first pass. Each averaging operation of this pass takes the averaged positions to the target value.

Note that this proposition generalises your property 2 (take $m=p$, $n=a$, $s = \tfrac bp$, $t=1$) as well as your property 4 (take $m=n=y$, $s=t=x$).

Corollary:

Given $a$, we can find $b < a$ such that $b \preceq a$ iff $a$ is not squarefree.

Clearly if $a$ is squarefree then from $p \mid a \implies p \mid b$ the smallest predecessor of $a$ is itself. On the other hand, if $a = p^2 a'$ then we can take $m = p$, $n = pa'$, $s = a'$, $t = 1$, $b = pa'$ in the three-pass lemma. (This is also an instance of your property 2).

Peter Taylor
  • 7.2k
  • 1
  • 21
  • 29