Let $p(x) \in \mathbb{Z}[x]$, such that $\deg (p) \ge 3$.
Can we always find $q(x) \in \mathbb{Z}[x]$, such that $\deg (q) < \deg(p)$ and $p(q(x))$ is reducible over $\mathbb{Q}[x]$?
Is there any algorithm to find $q(x)$?
Note that the degree of $q$ is less than degree of $p$.
I'm looking for a proof or any reference of this result.
Any help would be appreciated.
Note: in this answer, I have inadvertently disregarded your requirement for $q$ to have integral coefficients. I do however prove that a $q$ with rational coefficients does exist, so I will just let this answer be on here for the moment.
To answer your main question, yes this is possible (and simple to prove). We may assume $p$ irreducible, otherwise there is nothing to prove. Let $\alpha$ be a zero of $p$ and consider $K = \mathbb{Q}(\alpha)$. Now the subset $S$ of $K$ consisting of elements $\beta$ such that $\mathbb{Q}(\beta)=K$ is equal to the complement in $K$ of a finite number of lower-dimensional $\mathbb{Q}$-vector spaces; in particular it is non-empty. Likewise, the subset $T$ of $K$ consisting of all elements that are linearly independent over $\mathbb{Q}$ with $\{1, \alpha\}$ is also a complement of a finite number (in this case just one) of lower-dimensional vector spaces (here we need the degree of $p$ to be at least $3$).
Now take any $\beta$ in $S \cap T$ (which is non-empty by what I wrote above): since $\mathbb{Q}(\beta)=K$, we have $\alpha=q(\beta)$ for some $q$ in $\mathbb{Q}[X]$ whose degree we can choose to be $< \deg (p)$ by subtracting the appropriate multiple of the minimal polynomial of $\beta$. Since $\beta$ is in $T$, we have that the degree of $q$ is $>1$. Then $\beta$ is a root of the polynomial $p \circ q$, so the latter must have a factor of degree $\deg (p)$, whereas its degree is $\deg(p)\deg(q)>\deg(p)$. Hence it is reducible.
