
The answer depends on the true proportion in the population, your required significance level and the statistical properties of the binomial distribution.
The figure above shows the minimum respondents you would need to sample, as a function of the true population proportion. If the true proportion is between, say, 3.5% and 4.0%, you would need to sample around 1000 respondents, before a statistician using a one-sided 95% confidence band would announce your party a viable proposition.
You can go about this in a dynamical fashion. Sample 500 respondents. If the mean proportion is below ~4.7%, then sample another 500. If the new calculated mean stays above ~3.7% you are fine.