7
$\begingroup$

Let $n \in \mathbb{N}$ be a positive natural number and denote by $f(n)$ the number of decompositions of $n$ of the form $n = a+b+c+d$ where $a,b,c,d > 0$ are also positive natural numbers such that $ad-bc = 1$.

Is there a closed or a recursive formula for $f(n)$?

Improve this question
$\endgroup$
16
  • 4
    $\begingroup$ Are you counting ordered or unordered partitions, i.e. do you count 10 = 1+2+3+4 and 10 = 4+3+2+1 as the same or as two distinct decompositions? $\endgroup$
    – Stefan Kohl ♦
    Commented Feb 23, 2023 at 15:11
  • 2
    $\begingroup$ I want to take the order into account. So the partitions of $10$ you wrote are different. I added a condition on $a,b,c,d$ to my question. $\endgroup$
    – Puzzled
    Commented Feb 23, 2023 at 15:19
  • 3
    $\begingroup$ @PeterTaylor Thanks, with this correction for the first 30 values I get $\{0,0,0,0,2,0,4,2,4,2,8,2,10,4,6,6,14,4,16,6,10,8,20,6,18,10,16,10,26,6\}$ which seems to correspond to $f(n)=\text{A181830}(n)+\text{A070824}(n-1)$ except for $n=1$ (see oeis.org/A070824 ). $\endgroup$
    – Steven Clark
    Commented Feb 23, 2023 at 17:28
  • 4
    $\begingroup$ @StevenClark, for $n > 2$ that simplifies to $f(n) \stackrel{?}{=} \varphi(n) - 2$, which holds for $3 \le n \le 4500$. $\endgroup$
    – Peter Taylor
    Commented Feb 23, 2023 at 21:55
  • 2
    $\begingroup$ I suggest to additionally allow $a, b, c, d$ to be $0$, and show that with this convention, $f(n) =\varphi(n)$ for all $n>1$ (equivalently, when disallowing $0$, $f(n) =\varphi(n)-2$ for all $n>2$ as observed by Peter Taylor) . Indeed, there seems to be a 1-1 correspondence between such $(a, b, c, d)$ and coprime residues mod $n$ via $(a, b, c, d) \mapsto a+b$. Surely this can be seen via some simple trick? $\endgroup$
    – Joachim König
    Commented Feb 24, 2023 at 5:33

2 Answers 2

Reset to default
7
$\begingroup$

Let us show that $f(n) = \phi(n)$ if we allow $a,b,c$ and $d$ to be $0$ as @JoachimKönig suggested. The equality $ad - bc = 1$ is equivalent to $nd - (b + d)(c + d) = 1$. Let us show that for every $s\le n - 1$ coprime with $n$ there exists a unique answer to the initial problem satisfying $c + d = s$. Indeed, we need to solve $nd - (b + d)s = 1$. We have $d = n^{-1}$ mod $s$ and $c = s - d$. Also $b = (nd -1)/s - d$, notice that it is nonnegative. Finally, number $a$ is defined as $n - b-c-d$, and it is also nonnegative, otherwise $ad - bc = 1$ will not hold.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ As $a,d≠0$, only $b, c$ can be zero respectively when $s=n-1$ and $s=1$. Hence, for all $a,b,c,d≠0$ those two cases are eliminated, meaning $f(n)=\phi(n)-2$. $\endgroup$
    – Alapan Das
    Commented Feb 24, 2023 at 8:22
1
$\begingroup$

Here is a geometrical approach.

The expression $ad - bc$ is a determinant of matrix $ M =\left(\begin{smallmatrix} a &b \\ c &d\end{smallmatrix}\right)$ and $n$ is a sum of coordinates af the point $X = Mv_1$, where $v_1 = \left(\begin{smallmatrix} 1 \\ 1\end{smallmatrix}\right)$. The problem is equivalent ot the following

Statement. Let $X = (p, n - p)$ be a point on the line $x + y = n$ with non-negative integer coordinates.

  • If there exists matrix $M$ with $\text{det}M = 1$ such that $Mv_1 = X$ then $(n, p) = 1$;
  • If $(n, p) = 1$ then there exists a unique matrix $M$ with the same properties.

Proof: We start with the first part. Denote $v_2 =\left(\begin{smallmatrix} 1 \\ 0\end{smallmatrix}\right)$ and let $Y = Mv_2$ be the image point of $v_2$.

Matrix $M$ has unit determinant hence it preserves the area and consequently $S_{XOY} = \frac{1}{2}$. Now from the Pick's theorem applied to the $XOY$ we get that there are no integer points on the segment $OX$ except $O$ and $X$; therefore $(p, n - p) = 1$.

Now assume that $p$ and $n$ are coprime. To show the existence take $Y$ as a vertice of a triangle with the smallest possible area $S_{OXY}$. Again, by Pick's Theorem, its area equals to $1/2$ and therefore $\text{det} M = 1$.

Uniqueness can be show as follows: assume that there are two different points $Y_1$ and $Y_2$.

Equality of the areas implies that $OX\parallel Y_1Y_2$. However the segment $Y_1Y_2$ is shorter than $OX$.Thus, the point $Y_3$ corresponding to the vector $Y_2 - Y_1$ (or $Y_1 - Y_2$) is on the segment $OX$, which is a contradiction.

Improve this answer
$\endgroup$
4
  • $\begingroup$ If $n$ denotes an even integer and $p$ a prime, can we relate this to Goldbach's conjecture? $\endgroup$
    – Sylvain JULIEN
    Commented Mar 1, 2023 at 17:14
  • $\begingroup$ @SylvainJULIEN, I guess Goldbach's conjecture can reformulated in terms of the existence of matrix $M$ with condition on the sum of its elements and the image of the vector $v_1$ $\endgroup$
    – Pavel Gubkin
    Commented Mar 1, 2023 at 20:22
  • $\begingroup$ I've been thinking for some time about a way to prove that 1) every large enough even integer which is the sum of one, two or four squares is the sum of two prime powers and 2) every large enough even integer which is the sum of two primes powers is the sum of two primes. Taking squares as entries of the matrix would entail their positivity. $\endgroup$
    – Sylvain JULIEN
    Commented Mar 1, 2023 at 20:41
  • $\begingroup$ Also such matrices are elements of the modular group, so a connection with modular forms and possibly GRH for their L-function might be possible. $\endgroup$
    – Sylvain JULIEN
    Commented Mar 1, 2023 at 20:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .