4
votes
1answer
215 views

Existence of a certain subset of natural numbers equidistributed modulo $m$ for every $m$

I was talking to a friend and the following set $S$ came up. Let $f$ be some real valued function tending to infinity. Let $S$ be a subset of natural numbers such that $|S \cap [1,N]| = N^{\delta}+ ...
1
vote
1answer
208 views

An infinite product: combinatorial interpretation

It is an undergraduate exercise to show that the generating function for the sequence of unrestricted integer partitions $p(n)$ is the celebrated infinite product ...
3
votes
0answers
82 views

Number cubes with consecutive line sums

This is barely of research interest, but I'd classify it as a curiosity with connections to combinatorics. The problem is to place integers in an $n \times n \times n$ array so that all $3n^2$ line ...
0
votes
0answers
105 views

Base-signed harmonic series

This question is directly related to this question by Douglas Zare. The harmonic sequence $$s = 1 - \frac{1}{2} - \frac{1}{3} + \frac{1}{4} - \frac{1}{5} + \frac{1}{6}+\frac{1}{7}-\frac{1}{8} - ... ...
34
votes
6answers
2k views

Placing numbers $1,2,\ldots,n^3$ in a cube so that numbers of any two adjacent unit subcube are coprime

This is a question first I asked in SE but since there was no suggestion or solution, I decide to put it here. Consider an $n\times n \times n$ Cube containing $n^3$ unit cubes. Is it possible to ...
2
votes
2answers
761 views

Number of 1 in binary representation of n

Let $1(n)$ be the number of digits $1$ in binary representation of number $n$. For example, $13=1101_2$ so $1(13)=3\\$ Is there explicit form of $\,\,\sum{1(i)x^i} $? I checked OEIS and didn't find ...
9
votes
3answers
697 views

Could a perfect squared square be split into two perfect squared squares?

This is a geometric puzzle though it might conceivably also define a special class of Pythagorean triples. A perfect squared square PSS is a square (as a plane figure) partitioned into smaller ...
4
votes
1answer
323 views

Balog-Szemeredi-Gowers with dilates of sets

All sets are assumed to be finite subsets of the integers. The additive energy of two sets $E(A,B)$ is defined as the number of solutions to $a+b=a'+b'$ with $a,a'\in A$ and $b,b'\in B$. The ...
1
vote
1answer
167 views

Simplifying a sum in terms of divisor function Cauchy products

I'm trying to simplify this combinatorial looking sum: $$\sum_{ax+by=n}_{(a,x,b,y)\in \mathbb{N^4}}\max{\{a,b\}}$$ In terms of possibly some scaled divisor functions plus a Cauchy product/convolution ...
3
votes
0answers
125 views

What is the function like when its Mobius inversion is $\sum_{w|r, (w,t)=1}\mu(w)q^{r/w}$?

Everyone, I am now reading a paper named The Irreducible Factors of $(cx+d)x^{q^m}-(ax+b)$ over $GF(q)$, http://qjmath.oxfordjournals.org/content/14/1/61.extract. And I’m confused with one of its ...
5
votes
1answer
258 views

Number of partitions whose blocks form arithmetic progressions

As is known, the set $\{1,\ldots,n\}$ has $2^n$ many subsets and $B_n$ (the $n$th Bell number) many partitions, where clearly $B_n<2^{2^n}$ and it is actually known that $B_n<n^n$ for large $n$. ...
0
votes
0answers
47 views

A lower bound on the number of matrices whose image contains all multiples of $p^e$

Let $0\leq e<e^\prime$ be integers. Now suppose $N$ is the number of $n\times n$ matrices over the ring $R:=\mathbb{Z}/p^{e^\prime}\mathbb{Z}$ (where $p$ is prime) such that ...
8
votes
0answers
115 views

Erdös-Fuchs Theorem for multivariate linear forms

Let $A$ be an infinite set of positive integers, and denote by $r(n)$ the number of solutions to the equation $a+a'=n$, with $a,\, a' \in A$. It is not very difficult to show that if $r(n) > 0$ ...
7
votes
2answers
802 views

Linear independence of the square roots over Q

Does there exist a real number $a$ such that the numbers $\sqrt{n^2 + a^2}$ (for all natural $n$) are linearly independent over the field of rational numbers? It is evident that $a$ cannot be ...
0
votes
0answers
37 views

Minimize $td-2\sum_{i=0}^{t-1} w_k(i)$ where $w_k(i)$ is the sum of the base-$k$ digits of $i$

Let $K_k^n$ denote the $n$-fold cartesian product of the complete graph on $k$ vertices, and let $[R,T]$ be the edge cut, consisting of the edges between complementary vertex sets $R$ and $T$. I ...
3
votes
2answers
380 views

summation of products of combinatorials

For any natural number $N$ and $0\le n\le N$ define $$ f(n) = f(n,N) = \frac{1}{(N+1)!} \sum_{\substack{{S\subset \{1,\ldots,N\}} \\ {|S|=n}}} \prod_{s\in S} s. $$ (The empty product is interpreted ...
1
vote
1answer
199 views

Known results on cyclic difference sets

Is there any infinite family of $v$ for which all the $(v,k,\lambda)$-cyclic difference sets with $k-\lambda$ a prime power coprime to $v$ have been determined? A subset $D=\{a_1,\ldots,a_k\}$ of ...
3
votes
1answer
434 views

Estimate the sum $\sum_{k=1}^n \frac{2^k}{k}$ [closed]

I am concerned with the following sum $$\sum_{k=1}^n \frac{2^k}{k}_{\displaystyle ~.}$$ It seems that sum must be computed by someone, but I do not know. By the way, I can figure out a power ...
3
votes
0answers
55 views

Distribution of the evaluation (at a non-trivial root of -1) of polynomials with small coefficients

When we studied some cryptographic protocol, we came accross the following problem, which seems linked to the uniformity of the residues of small multiplicative subgroups of $\mathbb{F}_q$. Problem ...
7
votes
2answers
271 views

Sets whose elements are mutually “weakly” coprime?

Fix $n$ and $k$. I want a set $S\subseteq\{1,\ldots,n\}$ with the property that for every $x\in S$, $$\mathrm{gcd}\bigg(x,\prod_{y\in S\setminus\{x\}}y\bigg)<\frac{x}{k}.$$ How small should a ...
3
votes
1answer
263 views

A partition problem

This question is motivated by an old math contest problem, and is a generalization of the original problem. I will write out the original problem as motivation. Let us say that $n$ is $p$-Savage, for ...
1
vote
0answers
66 views

Quadratic transformation of hypergeometric function 2F1

I want to know whether there is some transformation between $_2F_1(a,b;c;x)$ and $_2F_1(a',b';c';x(1-x))$. Here is an example called the Kummer quadratic transformation, which may be known to most of ...
20
votes
3answers
2k views

How many different numbers can be obtained as product of first $n$ natural numbers?

Let m and n be natural numbers, and consider the set of all possible products of m (not necessarily distinct) elements from the set $\{1,2,\ldots,n\}$, that is consider the set $\{1^{a_1} \cdot ...
4
votes
1answer
393 views

a conjecture in sum-free sets

Let $ A $ be a set of non-zero integers. Then $A$ contains a sum-free subset $B$ of size $ |B|> \frac{|A|}{3} $ (a result of Erdős). It is conjectured that RHS can be improved to $\frac{|A|}{3} ...
0
votes
0answers
94 views

Multivariate generating function

I am investigating the perturbation of the Jordan canonical form. In my work I must calculate the number of ways to factor $p^ {n-k} q^k$ where $p$ and $q$ are distinct primes ...
19
votes
1answer
493 views

Avoiding multiples of $p$

Let $p$ be a prime number and $P=\{1,2,...,p-1\}$ In how many ways we can sum all the elements of $P$ in such a way that we will reach a multiple of $p$ only when we sum the last summand? For ...
8
votes
3answers
354 views

On the vanishing of the generalized von Mangoldt function $\Lambda_k(n)$ when $n$ has more than $k$ prime factors

It is a well-known fact that the generalized von Mangoldt function, defined by $$\displaystyle \Lambda_k(n) = \sum_{d | n} \mu(d) \left(\log \frac{n}{d}\right)^k$$ vanishes whenever $n$ has more ...
16
votes
1answer
570 views

A Question on 1, 2 ,3 Conjecture

1, 2, 3 conjecture is well-known: If $G$ is a simple graph which is not $K_2$ then one can assign a number among $1, 2, 3$ to every edge such that if we label each vertex with the sum of the numbers ...
3
votes
1answer
276 views

Combinatorial Technique Needed

The following problem is likely too special for MO. However I have no clue how to deal with it, so I'll just try. Nevertheless it is a combinatorial problem and a discussion about general methods in ...
0
votes
0answers
140 views

special values of L-functions cohen-lenstra heuristic

I found some lecture notes on links between number theory and random permutations. It was difficult to follow: The notes start with an interesting fact, whose proof I've asked on Math.StackExchange: ...
16
votes
2answers
922 views

Infinitely many $N$ such that $\langle p\rangle=\langle q\rangle$ mod $N$

Suppose that $p,q>1$ are two relatively prime integers. Are there infinitely many positive integers $N$ such that $N$ is relatively prime to $p$ and $q$; there exists positive integers $k,l$ such ...
11
votes
1answer
235 views

A Product Related to Unrestricted Partitions

Start with the product for unrestricted partitions: (1+x+x$^2$+...)(1+x$^2$+x$^4$+...)(1+x$^3$+x$^6$+...)... Now replace some of the plus signs with minus signs and expand the product into a ...
5
votes
0answers
186 views

2-adic Logarithm and Resistance of n-dimensional Cube

Resistance across opposite vertices of n-dimensional cube with each edge at one ohm resistance is $$R_n=\sum_{k=0}^{n-1}\frac1{(n-k){n\choose k}}=\frac1n\sum_{k=1}^{n}\frac1{{n-1\choose k}}.$$ The ...
2
votes
2answers
213 views

Irreducible Polynomials from a Reccurence

This question is inspired by a recent one : Let $c$ be a variable and define a sequence by $a_0=0$ $a_1=1$ and $a_{n+1}=a_{n}c-a_{n-1}$ . So $$\begin{align*} a_2 &= c \\ a_3 &={c}^{2}-1= ...
2
votes
1answer
534 views

The smallest altitude amongst the triangles formed by points in the unit circle

Let $S$ be a finite set of points inside the unit circle. Consider all possible triangles formed by three distinct points in $S$, and among all such triangles find the smallest altitude. Denote this ...
3
votes
1answer
265 views

Number of 3-tuple partitions of a multiple of three which follow the triangle inequality

Given n=3t, t$\in \mathbb N$; let $\mathbb L_3$ be set of all distinct integer partitions of n having 3 parts; say $\lambda_1,\lambda_2,\lambda_3$ . If I chose any one partition randomly from ...
6
votes
1answer
400 views

Estimating the number of non-negative integer $n$-tuples satisfying two conditions

I am interested in computing the number of non-negative integral $n$-tuples $(x_1, \cdots, x_n)$ satisfying the following two conditions, as a function of the parameters $D,T, w_1, \cdots, w_n, v_1, ...
8
votes
2answers
811 views

Proving $\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}$

I found the following formula in a book without any proof: $$\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}.$$ This does not seem to follow immediately from the basic ...
11
votes
3answers
884 views

A problem on a specific integer partition

Let $n$ be a positive integer, we consider partitions of the following form : $$n = d^{2}_{1} + d^{2}_{2} + ... + d^{2}_{r}$$ such that : $d_{i}\vert n$ $1=d_{1}<d_{2} \le d_{3} \le ... \le ...
1
vote
3answers
652 views

Number of subsets with fixed cardinality k, and sum of elements a multiple of m

I need some help on a problem on combinatorics. Let $n$ be a natural number greater than $1$ and $k,m$ be two fixed natural numbers not exceeding $n$ with $m\leq\frac{k(k+1)}{2}$. Let ...
2
votes
1answer
216 views

Simple approximation to a sum involving Stirling numbers?

I have also posted this question at http://math.stackexchange.com/questions/486917/simple-approximation-to-a-sum-involving-stirling-numbers. I have an exact answer to a problem, which is the function: ...
37
votes
2answers
1k views

Numbers that are generic w.r.t. exponentiation

This is a follow-up to my old question Number of distinct values taken by $x\hat{\phantom{\hat{}}}x\hat{\phantom{\hat{}}}\dots\hat{\phantom{\hat{}}}x$ with parentheses inserted in all possible ways. ...
5
votes
1answer
238 views

Identity on Gauss sums

I'd like to ask how to prove or disprove the following identity (which I have to use on some computation regarding $\epsilon$-constant for constructing certain local Langlands parameter): Let $\psi$ ...
0
votes
2answers
446 views

An extremal combinatorics problem over Finite Rings

Cross Posting from: http://math.stackexchange.com/questions/462016/a-combinatorics-problem-over-finite-rings Consider the set $S$ of all non-zero vectors over $\Bbb Z_{q}$ of length $r$ whose ...
1
vote
1answer
283 views

Valid Difference Sets

Suppose $$ P \subseteq \{1,2,\dots,N\},\quad |P| = K $$ We calculate the differences as: $$ d=p_i-p_j\mod N,\quad i\ne j $$ Now let $a_d$ denote the number of occurrence of $d$ (for $d = 0, 1, 2, ...
17
votes
3answers
762 views

Is the sequence of partition numbers log-concave?

Let $p(n)$ denote the number of partitions of a positive integer $n$. It seems to me that we have for all $n>25$ $$ p(n)^2>p(n-1)p(n+1). $$ In other words, the sequence $(p(n))_{n\in ...
0
votes
1answer
340 views

How to do such a partitioning?

Assume: $$ P \subseteq \{1,2,\dots,N\},\quad |P| = K, \qquad x \in \mathbb{R}_+^K , \qquad w = e^{-j\frac{2\pi}N} $$ and, $$ f(l) = \sum_{i=1}^K \sum_{j=1}^K x_i x_j w^{(p_i-p_j)l} $$ I am going to ...
-3
votes
1answer
170 views

How to prove that homometric sets lead to same result in this problem? [closed]

First let me define Difference multiset for a set of integers $$P=\{p_1,p_2, \dots,p_K\} ,\quad p_i \in\{1,2,\dots,N\},\quad p_i\ne p_j $$ as below: $$ D = \{p_i-p_j \mod N ,\quad i \ne j\} $$ I ...
3
votes
2answers
581 views

A problem about Determinant of sum of permutation matrices

Let $w_1$ and $w_2$ be two permutations of $\{1, \cdots , k\}$ such that for all $1\leq i \leq k$, $w_1(i)\neq w_2(i)$. Let $m$ and $n$ be two relatively prime integers. Then is there exist two ...
30
votes
2answers
1k views

A question on maps from $\mathbb{Z}/p\mathbb{Z}$ to itself

Let $p\geq 3$ be a prime number, and let $u:\mathbb{Z}/p\mathbb{Z}\to \mathbb{Z}/p\mathbb{Z}$ be a map such that, for all $l\in \mathbb{Z}/p\mathbb{Z}$,$l\neq 0$, the map $k\mapsto u(k+l)-u(k)$ is a ...