13
$\begingroup$

I recently encountered the following equality ($\{\}$ denotes fractional part):

$$\sum_{k=1}^{65}k\left\{\frac{8k}{65}\right\}=\sum_{k=1}^{65}k\left\{\frac{18k}{65}\right\}$$

and found it very interesting as most of the individual summands on one side of the equation do not have a corresponding match on the other side. Investigating further, I found several other similar equalities:

$$\sum_{k=1}^{77}k\left\{\frac{9k}{77}\right\}=\sum_{k=1}^{77}k\left\{\frac{16k}{77}\right\}$$

$$\sum_{k=1}^{77}k\left\{\frac{17k}{77}\right\}=\sum_{k=1}^{77}k\left\{\frac{24k}{77}\right\}$$

$$\sum_{k=1}^{85}k\left\{\frac{7k}{85}\right\}=\sum_{k=1}^{85}k\left\{\frac{22k}{85}\right\}$$

Does anyone have any idea what general principle/pattern these arise from?

$\endgroup$
12
  • $\begingroup$ It may help to rewrite it like this: $\sum_{k=1}^{n}k\{\frac{ak}{n}\} = \sum_{k=1}^{n}k\frac{ak \mod n}{n}$ $\endgroup$ Commented Jul 21, 2014 at 12:37
  • $\begingroup$ @MichaelStocker And then you can remove the division, since it just scales the values... $\endgroup$ Commented Jul 21, 2014 at 12:40
  • $\begingroup$ What does it look like when you write it in terms of Dedekind sums? $\endgroup$ Commented Jul 21, 2014 at 13:05
  • $\begingroup$ It's interesting that, in the examples I've run (still relatively small) there are always $1,2,$ or $4$ numerators that yield the same value, but never $3$ or more than $4$. I've only been checking denominators that are a product of two primes. $\endgroup$ Commented Jul 21, 2014 at 14:30
  • $\begingroup$ When the denominator is divisible by $3$ distinct primes primes, you can find $6$ and $8$ numerators that yield the same value, but still no examples of a value reached by exactly an odd number of numerators, other than $1$... $\endgroup$ Commented Jul 21, 2014 at 14:37

3 Answers 3

2
$\begingroup$

Given $n$, let $a$ and $b$ be integers coprime with $n$. Then:

$$\sum_{k=1}^n k \left\{ \frac{ak}{n}\right\} = \sum_{k=1}^n k \left\{ \frac{bk}{n}\right\}$$

As Michael Stocker commented:

$$f(a,n) = \sum_{k=1}^n k \left\{ \frac{ak}{n}\right\} = \sum_{k=1}^n k \frac{ak \mod n}{n} = \frac{1}{n}\sum_{k=1}^n k (ak \mod n)$$ $$f(b,n) = \sum_{k=1}^n k \left\{ \frac{bk}{n}\right\} = \sum_{k=1}^n k \frac{bk \mod n}{n} = \frac{1}{n}\sum_{k=1}^n k (bk \mod n)$$

I've been able to prove that, as Thomas Andrews said, if $ab \equiv 1 \pmod{n}$ then $f(a,n) = f(b,n)$:

Let $k' := ak \mod n$ then $k' (bk' \mod n) = k (ak \mod n)$. Here's the proof: $k'[b(ak \mod n) \mod n] = k'(abk \mod n) = k'(k \mod n) = k'k = k(ak \mod n)$.

Note that $\lbrace (ak \mod n) \vert 1\leq k \leq n\rbrace = \lbrace 0, 1,2\cdots ,n-1\rbrace$.

So now $$f(a,n) = \sum_{k=1}^n k \left\{ \frac{ak}{n}\right\} = \sum_{k'=1}^n k' \left\{ \frac{bk'}{n}\right\} = f(b,n)$$

Now for the cases like $f(8,65) = f(18,65)$ where $ab \not\equiv 1$ I've found that $$k(ak \mod n) - k(bk\mod n) = \\(n-k)(b(n-k)\mod n) - (n-k)(b(n-k)\mod n)$$

But so far I've been unable to caracterize the pairs $(a,b)$ with that property.

$\endgroup$
6
  • $\begingroup$ But doesn't the first sum become $\sum_{k=1}^n k \left\{ \frac{bk'}{n}\right\}$ instead of $\sum_{k=1}^n k \left\{ \frac{bk}{n}\right\}$? $\endgroup$
    – N. S.
    Commented Jul 21, 2014 at 13:31
  • $\begingroup$ @N.S. It will become $\sum_{k'=1}^n k' \left\{\frac{bk'}{n}\right\}$ wich is equivalent... I think $\endgroup$
    – Darth Geek
    Commented Jul 21, 2014 at 13:34
  • $\begingroup$ No it doesn't. As you said, for each $k$ there exists a $k'$ so that $\left\{ \frac{ak}{n} \right\}= \left\{ \frac{bk'}{n} \right\}$. Which means that $k\left\{ \frac{ak}{n} \right\}$ becomes $k\left\{ \frac{bk'}{n} \right\}$.... $\endgroup$
    – N. S.
    Commented Jul 21, 2014 at 13:43
  • $\begingroup$ @N.S. You are absolutely right. I'll try to think a way to fix this. $\endgroup$
    – Darth Geek
    Commented Jul 21, 2014 at 14:06
  • $\begingroup$ @ThomasAndrews my proof is not right as pointed out in the comment. I'm trying to work out a fix. I think $a$ and $b$ must me coprime with $n$ but $a-b$ must not. $\endgroup$
    – Darth Geek
    Commented Jul 21, 2014 at 16:53
0
$\begingroup$

Here is a small GNU Maxima script to ease experimentation


    display2d : false;

    /* x rational */
    my_floor(x) := block(
        if (x >= 0) then block(
            ab : divide(ratnumer(x),ratdenom(x)),
            a : ab[1], b : ab[2],
            if (b = 0) then block(
                return(x)
            ) else block(
                return(x - b/ratdenom(x))
            )
        ) else block(
            ab : divide(ratnumer(-x),ratdenom(-x)),
            a : ab[1], b : ab[2],
            if (b = 0) then block(
                return(x)
            ) else block(
                return(x - (1-b/ratdenom(-x)))
            )
        )
    );

    /* x rational */
    my_frac(x) := x - my_floor(x);

    cz : 0; cnz : 0;
    for N : 1 thru 20 do block(
    for m1 : 1 thru 20 do block(
    for m2 : m1+1 thru 20 do block(
        mylhs : apply("+",makelist(k*my_frac(m1*k/N),k,1,N)),
        myrhs : apply("+",makelist(k*my_frac(m2*k/N),k,1,N)),
        if (mylhs - myrhs = 0) then block(
            cz : cz+1,
            print(N,m1,m2,"|",mylhs)
        ) else block(
            cnz : cnz+1
        )
    )));
    print(cz,"|",cnz);

$\endgroup$
6
  • $\begingroup$ Using the script above, I have found no solutions with $1 \le N,m1,m2 \le 100$, $gcd(N,m1) \neq 1$, $gcd(N,m2) \neq 1$, $gcd(m1,m2) = 1$. $\endgroup$
    – andre
    Commented Jul 21, 2014 at 15:22
  • $\begingroup$ What do you mean by "no solutions?" Do you mean no more solutions than the ones above? $\endgroup$ Commented Jul 21, 2014 at 18:30
  • $\begingroup$ Exactly what I've said. I have found no solution for $1 \le N,m1,m2 \le 100$ with the additional conditions $gcd(N,m1) \neq 1$, $gcd(N,m2) \neq 1$ and $gcd(m1,m2) = 1$. You may substitute $m1=a$ and $m2=b$. $\endgroup$
    – andre
    Commented Jul 21, 2014 at 19:00
  • $\begingroup$ Sorry, reading comprehension failure on my part - read $\neq$ as $=$... $\endgroup$ Commented Jul 21, 2014 at 19:45
  • $\begingroup$ Because of my low reputation, I comment here. I believe we should identify the pattern of the function $f(n,m,k) := (n-m)/n - \{mk/N\} + \{m(k+1)/N\}$ in order to perform a summation by parts. $\endgroup$
    – andre
    Commented Jul 22, 2014 at 22:41
0
$\begingroup$

[Raw data deleted.]

Defining $$f(a,n)=\sum_{k=1}^{n-1} k\left\{\frac{ka}{n}\right\}$$ it's pretty obvious that $f(a,n)+f(n-a,n)=\frac{n(n-1)}{2}$ when $(a,n)=1$. It's also true, as proven by Darth Geek, that if $ab\equiv 1\pmod n$ then $f(a,n)=f(b,n)$.

Further data leads to:

Conjecture: If $f(a,n)=f(b,n)$ then $n\mid (a-b)(ab-1)$, or, equivalently, $a+a^{-1}\equiv b+b^{-1}\pmod n$, where the inverses are taken modulo $n$.

This would mean that the pairs $a,a^{-1}$ are the only solutions when $n$ a prime.

It is definitely not sufficient, since $a=3,b=48,n=65$ satisfies this condition.

This conjecture holds for all integers $4\leq n\leq 5000$.

$$\begin{align}f(a,n)&=\frac{a}{n}\sum_{k=1}^{n-1} k^2 - \sum_{k=1}^{n-1} k\left\lfloor\frac{ka}{n}\right\rfloor\\ &=\frac{a(n-1)(2n-1)}{6} - \sum_{k=1}^{n-1} k\left\lfloor\frac{ka}{n}\right\rfloor \end{align}$$

Thus $f(a,n)$ is an integer if $(n,6)=1$.

$\endgroup$
3
  • $\begingroup$ Perhaps the condition is sufficient for prime $n$? It's just a guess since for prime $n$ the sum may behave nicer. $\endgroup$ Commented Jul 22, 2014 at 10:57
  • $\begingroup$ For prime $n$, that means $ab=1$ or $a=b$, and that does appear to be sufficient in that case, with the data I'm looking at. @barto $\endgroup$ Commented Jul 22, 2014 at 12:16
  • $\begingroup$ Thank you, that's interesting. Understanding the behavior for prime $n$ would be a good step forward. $\endgroup$ Commented Jul 22, 2014 at 18:45

You must log in to answer this question.

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